Nested loop Running Time?

Question

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?

Just FYI - your posts are being discussed on Meta.SO: meta.stackoverflow.com/q/323749/607407 — Tomáš Zato
– Tomáš Zato, Commented May 25, 2016 at 10:04

Ilia Maskov · Accepted Answer · 2016-02-20 08:54:39Z

4

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

answered Feb 20, 2016 at 8:54

Ilia Maskov

1,91816 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Nested loop Running Time?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related