CODEWITHSUNDEEP
performancealgorithmdata-structuresruntimebig-o
blah blah
blah blah

Reputation: 39

Big O Run Time for nested loops?

How do you calculate the big O run-time efficiency for this code? My gut tells me it is O(n^3) but I'm not sure, as I'm not really sure if the loops are independent or dependent.

for (i=1; i<=n; i++)
    for (j=1; j<=n; j++)
        for (k=1; k<=n; k++)
          print ("%d %d %d/n", i, j, k);

Upvotes: 0

Views: 266

Answers (2)

Travis
Travis

Reputation: 2757

Yes, this function would be O(N^3) because inside each loop you are running N iterations.
The loops are not independent, because they are nested.

N * N * N = N^3

Upvotes: 0

Ekotlikoff
Ekotlikoff

Reputation: 23

Your gut feeling is right. You have three nested for loops iterating over n, so for each of the first n loops you make another n loops, each of which in turn make n more loops. Thus O(n^3).

Edit: think about how this will play out- i is first 1, j 1 as well, and then k loops 1 through n. Only after k has undergone that whole loop, will j increment to 2, then k undergoes the loop once again and so on.

Upvotes: 1

Related Questions