CODEWITHSUNDEEP
algorithmbig-otime-complexity
maxicecil21
maxicecil21

Reputation: 11

Running time for this for loop statement?

I am trying to figure out the Big-O run time for this loop statement. Can somebody help me out?

for (i = 1; i < n*n; i=i*2)

Is it O(n^2 lg n)?

Upvotes: 1

Views: 132

Answers (3)

Denis
Denis

Reputation: 148

The answers proposed are correct; ìt is O(logn), because your iteration increment is polynomial (1, 4, 8, 16 etc..), not linear.

You can look at it like this - the number of iterations is not linear, but polynomial, which is in logaritmic proportion to the amount of iterations. Although the number of iterations is quadratic, it is constat during your loop execution, therefore the quantifier 2 in 2*O(logn) can be ignored.

Upvotes: 1

Rami Jarrar
Rami Jarrar

Reputation: 4643

Its O(logn) :

log(n^2) = 2log(n) = O(logn)

Upvotes: 2

Terry Li
Terry Li

Reputation: 17268

No, it should be O(logn). Because log(n^2) = O(logn).

Upvotes: 2

Related Questions