Complexity doubt

#1

Hi
How is the complexity O(n) because we are using nested loop?

#2

there are 2 method to solve this question
if you use nested loop then time Complexity will be O(N^2)
but if you use stack then time Complexity will be O(N)

#3

Yes,in the stack method only, we are using 2 nested loops, then how it is O(n)?

#4

inner loop never run N times
either it run 2 times or 3 times on average
sum of times the inner loop run is N

you can see it other way round
every element is inserted once and poped once
so total time it run is 2*N so time complexity will be O(N)

#5

If we use nested loop instead of stack, then also inner loop never run N times. So, in that case how it is O(N2)?

#6

Inner loop may run N times in that case
Example
5 4 3 2 1

#7

If we use stack, then also inner loop can run till end. Because if we are at 5 , then we may run till 1 (end of the array)??

#8

have you code it??

if you use stack then you never go in inner loop
because the condition s.top()<arr[i] never holds true

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#10

Please check this https://ide.codingblocks.com/s/46949

#11

if we never go in inner loop then why we are using it.?

#12

hello @vatsal50

u have reopend ur doubt. can u please once recheck ur shared link.
i think its having different code

#13

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.