CODEWITHSUNDEEP
algorithmbig-oasymptotic-complexity
33ted
33ted

Reputation: 699

Nested loop Running Time?

What is Running Time in Big oh notation of:

for(int i=1;i<N;i++)

    for(int j=1;j<N;j*=2)

The loop will stop when j > N. If we let k be some arbitrary iteration of the loop, the value of j on iteration k will be 2k. The loop stops when 2k > n, which happens when k > log2 n.

Therefore, the number of iterations is only O(log n), so the total complexity is O(log n).

Is this correct?

Upvotes: 1

Views: 463

Answers (1)

Ilia Maskov
Ilia Maskov

Reputation: 1898

The O(n) for the outer loop and O(log(n)) for the inner one. So the total is O(n*log(n)).

Upvotes: 4

Related Questions