Resolved: Iam still confused how time complexity is calculated

In this post, we will see how to resolve Iam still confused how time complexity is calculated

Question:

For the below code it is said that the time complexity is O(n^2)
If the inner loop runs for n*n times and outer loop runs for n times then shouldn’t it be O(n^3)
But similarily for below code,the time complexity is O(n^3)
So can someone explain the reason ?
I felt that time complexity for the cases should be O(n^3) but that’s not the case.

Best Answer:

You are right in the case of the second example, the time complexity is O(n^3) since the outer loop iterates n-1 times and inner one n^2 which results in (n-1) * n^2 or n^3 – n^2 so considering constant time operations the complexity can be expressed as O(n^3).
However in the first example the complexity is only O(n^2) which reflects the number of iterations of the inner loop since the outer loop will always execute only once. This is because the inner loop will exit with i=n*n-1 after the first iteration of outer loop which is outside the first loop’s bounds (i < n).

If you have better answer, please add a comment about this, thank you!

Source: Stackoverflow.com