Question

Here again is the function from the previous question. Using big-oh notation, what is the best-case runtime for this function?

int is_sorted( int *array, int n)

{

int i;

for (i = 0; i < n - 1; i++)

if (array [i] > array [i + 1])

return 0;

return 1;

}

Answer 1

Given code snippet tests if the array is sorted in non-decreasing order

int is_sorted( int *array, int n)
{
    int i;
    for (i = 0; i < n - 1; i++)
        if (array [i] > array [i + 1])
            return 0;
    return 1;
}

This function itarates through all the elements in the array and compares adjacent elements'

In the best case, arr[0] > arr[1]. In this case we will get to know that the array is not sorted in non-decreasing order in the first comparision itself. So, complexity is theta(1) ,i.e exactly one comparision
In the worst case, we have iterate through all the elements in the entire array. (When array is sorted in non decreasing order)
So, time complexity is theta(N).
Average time complexity is O(N)