CODEWITHSUNDEEP
c++algorithmtime-complexitybig-o
HeyItzSteve
HeyItzSteve

Reputation: 3

Time Complexity of nested for loops with different conditions

What would be the time complexity for this snippet? I'm having a little trouble understanding how to find the time complexity of nested for loops with different conditions.

I originally thought that it would be n^3 x n^2 which gives O(n^5), but should it be (n^3)^2 which gives O(n^6)?

for(int i = 0; i < n*n; i++) {
    for(int j = 0; j < n*n*n; j++) {
        A(); //O(1)
    }
}

Upvotes: 0

Views: 80

Answers (1)

ShadowRanger
ShadowRanger

Reputation: 155343

If you correctly incremented j in the inner loop (replacing i++ with j++ in the inner loop increment step), it would be O(n⁵). The outer loop runs the inner loop n² times, with each inner loop running n³ times; the total is strictly multiplicative, n² * n³ == n⁵.

As written, it'll never stop running if n > 1 (because j never increments, so if the inner loop begins running, it runs forever).

Upvotes: 1

Related Questions