What is the time complexity of the below function?

Question

void fun(int n, int arr[])
{
int i = 0, j = 0;
for(; i < n; ++i)
    while(j < n && arr[i] < arr[j])
        j++;
}

The answer given is: variable j is not initialized for each value of variable i, so time complexity is O(n)

I don't quite understand it. Can anyone explain?

Answer 1

The outer loop is executed n times.

The inner loop only continues if j < n, and since j is incremented in each step, it cannot be executed more than n times in total.

Answer 2

See the difference between your function and this (this is in O(n²) time complexity) -

void fun(int n, int arr[])
{
    int i = 0, j = 0;
    for(; i < n; ++i)
    {
        j = 0;
        while(j < n && arr[i] < arr[j])
            j++;
    }
}

In your function the variable j is not initialized for each value of variable i. So, the inner loop runs at most n times.

Edit 1- From j=0 to j=n is maximum n iterations of inner while loop. Since you never initialize j again once j=n the inner while loop will never iterate. So at maximum (it could be less depending on the second condition arr[i] < arr[j]) you have n iterations of inner while loop once. The outer for loop will obviously iterate n times . So you have n+n=2n and not n2 even in the worst case.

Edit 2- @Kerrek SB answer to this is spot-on -
"The code finishes when j has been incremented n times. j never gets decremented, and at most n attempts are made at incrementing it (via i)"