How to determine the complexity of the snippet without knowing the array


#1

I don’t understand. The array values are not certain, how to determine the complexity of this snippet?


#2

This is what is asked for here:

I think you’ll need to understand that concept first.


#3

My approach -
I thought what could be the worst case scenario? so I constructed an array where a[i] < a[j].
Now go through the code. The complexity you get is the answer. So I would recommend think worst case first.


#4

Also, it’s a trick question. By reckless observation, the time complexity seems to be O(n^2). the second condition will be surely violated with j=i, independent of the array.


#5

Still, I don’t get how it’s O(n)


#6

Just look the condition when i=0 and j=0
while(j < n && arr[i] < arr[j]){}

the condition arr[i] < arr[j] is false, so while() dont run.

in next case when i=1 and j=0
so in worst case lets say while() runs again this time but while() will run once only as j become 1
the while condition will be false.

now i=2 and j=1
again j run once

overall in n iteration of i , while only run once in every iteration of i
so overall complexity is O(n)


#7

yes, I understood it now. I’m a noob in understanding the complexity of algorithms. Thank you, Suraz, for your detailed explanation.


#8

Thanks Suraz for explaining in detail. It helped me.


#10

While I agree with the rest of your answer, I would like to point out that in the next case when i=1, j won’t become zero because the 0 is never assigned to j.
And so j’s value is still equal to n. Hence, it will not go inside the while loop.


#11

Actually, I think the key point to this question is that j is a global variable.
For the inner loop, the worst case occurs when arr[i] >= arr[j]. This means two things. One, we can disregard the values in the array when doing worst case analysis for this problem. Two, the worst case is when the inner loop runs n times.

But, each time the loop runs, it increments j. Therefore, at the end of this worst case iteration, j = n. What does this mean about each subsequent iteration? Since j is a global variable that is never reset in the outer loop, the inner loop will not run again! So, instead of the inner loop running one time for each iteration of the outer loop – which is O(n^2) – the inner loop runs exactly once. The time is therefore O(2n), which is O(n) since we do not care about constants when doing worst case time complexity.