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
If the inner loop runs for
n*ntimes and outer loop runs for n times then shouldn’t it be
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!