CODEWITHSUNDEEP
performancetimetime-complexity
John
John

Reputation: 13

Can loops affect other loops' complexity without being inside it?

Can a loop affect any other loop without being inside it?

Will the total time complexity for the code be changed?

I found this code in the internet as an example for what I'm talking about:

int i, j, k, val=0, c=0;
for (int i=n; i>1; i=i/2)
    val++;
for (j=1; k<val; j=j*2)
    c++;

I thuoght that the time complexity for this code is n^2 but it seems I was wrong

Sorry for my English.

Upvotes: 1

Views: 45

Answers (1)

Patrick87
Patrick87

Reputation: 28302

Yes, it can, and in your example, it does. The first loop calculates some value used to determine the number of iterations the second loop will execute. The number of iterations is (related closely to) the complexity.

Currently, the first loop does ~log(n) iterations and the second does ~log(log(n)) iterations. If the first loop were changed to do ~n iterations, the second would do ~log(n). If the first were changed to calculate val in a way that made it ~2^n, the second loop would do ~n iterations.

There's nothing special about this other code being a loop: any code before a loop can affect the complexity of the loop.

Upvotes: 1

Related Questions