educative.io

Can someone explain why solution#2 is O(n)?

Courses
,
#1

I am not sure I agree on solution 2 being O(n), should it be O(n^2)?

#2

Hi @Hassan,

Thanks for your question. Can you please show us an input list for which the time complexity is in O(n^2)? That would help us evaluate this better.

Regaeds,
– Team Educative

#3

Hi @Coderust @Hassan
I am also confused about the time complexity of the second solution here. The outer loop takes n iterations, but the inner loop can also take few iterations. The inner loop time complexity can be O(k) where k is the number of pops for each iteration we have to do.

So shouldn’t the time complexity be O(n*k) rather than O(n).
And if k becomes n in some cases it becomes O(n^2). Although I doubt this scenario.

Can you please help?
I think the main confusion is about the inner loop as to how bad it could be.

Thanks,
Ankit

#4

Not sure if these two solutions count as O(n) or O(n^2), but they seem that they should take the same number of iterations. In Solution #1 the inner loop breaks once it finds the right element and in Solution #2 the while loop iterates as far as the right number which in both cases should be the same number of iterations.

Course: https://www.educative.io/collection/5642554087309312/5634727314718720
Lesson: https://www.educative.io/collection/page/5642554087309312/5634727314718720/5689765575786496

#5

Hi @Andreas !!
Both Solution 1 and Solution 2 have different time complexities and can be analyzed to determine their efficiency.

Solution 1:
In Solution 1, the algorithm uses a nested loop structure to find the next greater element for each element in the list. The outer loop iterates through each element, and the inner loop searches for the next greater element. In the worst case scenario, where there are no greater elements, the inner loop will iterate n-1 times for each element. Therefore, the time complexity of Solution 1 is O(n^2).

Solution 2:
In Solution 2, the algorithm uses a stack to efficiently find the next greater element for each element in the list. It iterates through the list in reverse order, and for each element, it compares it with the elements in the stack. The while loop in Solution 2 iterates at most n times (once for each element in the list), and each element is pushed and popped from the stack at most once. Therefore, the time complexity of Solution 2 is O(n).

To summarize, Solution 1 has a time complexity of O(n^2) while Solution 2 has a time complexity of O(n). Therefore, Solution 2 is more efficient in terms of time complexity as it only requires a linear number of iterations, making it the preferred solution for finding the next greater element in the list.
I hope it helps. Happy Learning :blush:

#6

It iterates through the list in reverse order, and for each element, it compares it with the elements in the stack. The while loop in Solution 2 iterates at most n times

If it iterates n times in reverse and for each element it compares with the elements in the stack in the while loop at most n times then it’s n^2 for Solution 2.

Course: https://www.educative.io/collection/10370001/5500262945128448
Lesson: https://www.educative.io/collection/page/10370001/5500262945128448/5362122985046016

Course: https://www.educative.io/collection/10370001/5500262945128448
Lesson: https://www.educative.io/collection/page/10370001/5500262945128448/5362122985046016