Time Complexity

Question

foo(int n, int a[])
    {
        int i=0,j=0;
        for(i=0;i<=n;i++)
        while (j<n && A[i]<A[j])
        j++;
    }

Time complexity of foo()

Comments

Consider an array completely sorted in ascending order now apply the code on it. when i =0, j will go from 0 to n time is O(n) and when j becomes n condition will be false, thus out of while loop. Now, iterate for i = 1, j is n condition false TC = O(1) again iterate i for i = 2, j is n while condition false TC = O(1) and so on.

$n + 1 + 1 + 1 + ........... + 1$

$n + n = O(n)$

---

@ Shubhanshu I have got few doubts..

1. Why will we consider it to be sorted when it is not mentioned anywhere.

2. How will j increment?

For 1st iteration, i=0 and j=0, j<n is T and A[i]<A[j] is F as both of them are same..so while loop breaks(j is not incremented) , control goes back to i, i=1 and j remains 0. This time j<n T but A[i]<A[j] is not certain to be false..if our assumption on the array to be already sorted is false.

---

I took sorted array to achieve its worst case because then only inner while loop will run from 0 to n-1 completely if you want to take any other configuration then also it will good.