Time complexity of the following Insertion + Search

I have following code for a scheduler. Each Task is registered via sched_register_task() function and this function is called from main. Each new task is placed in the array of tasks sorted and uses binary search for searching if the task is already present or not.

I know that binary search has complexity log(n) and sorting can be at best nlog(n). however this sorting is the case when there is one time sorting but in my case whenever a task is registered, it is inserted sorted.

I want to know the time complexity of registering a task.
so when want to register a task i write in my main

sched_register_task(&task_funct_1);
sched_register_task(&task_funct_2);
sched_register_task(&task_funct_3);

the functions are defined as follows

taskindex_info_t m_index[10];
task_info_t m_info[10];

uint8_t get_task_id(task_t task)
{
    check_structs_are_valid();
    assert(num_registered_tasks <= NUM_TASKS);
    int begin = 0;
    int end = num_registered_tasks - 1;
    uint32_t i = 0;

    while (begin <= end)
    {
        int pivot = begin + ((end - begin) / 2);

        if (((void*)m_index[pivot].task) < ((void*)task))
            begin = pivot + 1;
        else if (((void*)task) < ((void*)m_index[pivot].task))
            end = pivot - 1;
        else
        {
            return m_index[pivot].index;
        }
        i++;
        assert(i < 10000);
    }
    return NO_TASK;
}

error_t sched_register_task(task_t task)
{
    error_t retVal;
    check_structs_are_valid();
    if(num_registered_tasks >= NUM_TASKS)
        retVal = ENOMEM;
    else if(get_task_id(task) != NO_TASK);
        //retVal = EALREADY;
    else
    {
        int i = num_registered_tasks;
        for(i = num_registered_tasks; i >= 0; i--)
        {
            if (i == 0 || ((void*)m_index[i-1].task) < ((void*)task))
            {
                m_index[i].task = task;
                m_index[i].index = num_registered_tasks;
                m_info[m_index[i].index].task = task;
                break;
            }
            else
            {
                m_index[i] = m_index[i-1];
            }
        }
        num_registered_tasks++;
        retVal = SUCCESS;
    }
    check_structs_are_valid();
    return retVal;
}


Source: c#

Leave a Reply