Self Doubt

Question

<!--StartFragment -->

void fun(int n, int arr[])

{

    int i = 0, j = 0;

    for(; i < n; ++i)

        while(j < n && arr[i] < arr[j])

            j++;

}

 

In this question the inner loop runs n times at most because j is not initialised for every I. this makes complexity O(n) but wont the outer loop also run n times (incrementing and checking conditions in while) and making the total time complexity to be O(n2)??

<!--EndFragment -->

Comments

in best case it is O(n) only

Best case possible for the input in which descending  order.

But in worst case, it executes O(n*n)

Answer 1

Once value of J =n , innermost loop will not be executed. thus total  n + n-1 times the two loops run  - thus TC =  O(n)

Answer 2

Go through the following link

You can find my answer to this question in detail

https://stackoverflow.com/a/63492714/14132952