How the time complexity of this code is O(N)?

#1

I think time complexity should be O(N^2) because there is another while loop is running inside the for loop in the code written during the lecture…

#2

hello @abhi542136

keep following things in mind
a) in unorderd set every operation takes O(1) (on average) time.
b) if s1,s2…sm are the consecutive series present inside array then inner loop will run total
s1+ s2+s3+…sm times.

so total time complexity will be O(N + S1+S2+S3…+SM)
also keep in mind that S1+S2+S3…+SM is=N (sum of all elements)
so time complexity will be (N+N) -> O(2N)-> O(N)

1 Like
#3

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.