educative.io

Educative

Time complexity question Doubt in Big-O notation

Hello,

In the Big O notation topic, I see Challenge-6 and Challenge-7 to be same however the solution is proposed differently. Could you please explain?

Hi Kishore,
The difference between these two solutions is their time complexity. In challenge 6(advanced), time complexity is O(nlog2(n)), while in challenge 7(pro), time complexity is O(n). The time complexity of pro solution is better than the advanced solution.
O(n) < O(nlogn)

Hi Kanwal,
But the code is almost the same. how can time complexity of the inner loop in the 7 chanllenge be O(n) ? Shouldn’t it be O(logn)

in challenge 6 j is being set to 1 every time outer loop runs but its not the case in challenge 7

1 Like

Hi @samid_hamza, Thanks for reaching out to us.
In challenge 7 Nested Loop with Multiplication (Pro) the time complexity O(n) is not the complexity of the inner loop. The inner loop has a time complexity of O(log2(n)). The overall time complexity of the whole program is O(n).

Hope it will help :slight_smile:

1 Like

Hi @vineeth_sagar
The difference between pro and advanced solutions is their time complexity. In challenge 6(advanced), time complexity is O(nlog2(n)), while in challenge 7(pro), time complexity is O(n). The time complexity of the pro solution is better than the advanced solution.
So, don’t compare them like this, the time complexity of both solutions is calculated differently.
Hope it will help :slight_smile: