Time complexity for nested_cmpl


#1

Why time complexity is O(N * N)?
There three loops, so wouldn’t that be O(N * N + N)?
Thanks.


#2

@sem-babenko As per your logic It would be O(N*N) + O(N), being said that now take very very large inputs for N and look at the problem again. As the input grows exponentially the value of O(N) would be insignificant compared to the value O(N*N). So we would chuck the lower order terms. Now imagine and add another three nested for loop to this problem, the complexity becomes O(N*N*N) + O(N*N) + O(N) , again here for very large inputs O(N*N) and O(N) values will be insignificant compared to O(N*N*N) , so here we chuck the lower order terms O(N*N) and O(N)


#3

Since ,here the loop was nested. and and the complesity of nested loops depends upon the number of nested ladder.


#4

yes right the complexity of loops becomes on the nested ladder but here for large inputs we have to ignore the lower order terms leaving us with O(n^2).


#5

Time complexity video for solved examples - Click here