Time complexity for nested_cmpl


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


@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)


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


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).


Time complexity video for solved examples - Click here