Complexity of An Algorithm(Nested loops)

Question

I'm given code for an algorithm as such:

1  sum =0;
2    for(i=0; i<n; i++)
3      for(j=1; j<= n; j*=3)
4        sum++;

I'm told this algorithm runs in O(nlogn) where log is in base 3. So I get that the second line runs n times, and since line 3 is independent of line 2 I would have to multiply the two to get the Big O, however, I'm not sure how the answer is nlogn(log in base 3), is their a guaranteed way to figure this out everytime? It seems like with nested loops, there's a different case that can occur each time.

The O() runtime of the second loop, on its own, runs exactly (1/3) * n times, right? So this is better than O(n), but obviously constant, so we use log as an upper bound because it is in between. — James
– James, Commented Dec 6, 2015 at 3:02
with time complexity the base of the logarithm is of no relevance, thus it is eluded and simply O(log n) — Dimitar
– Dimitar, Commented Dec 6, 2015 at 3:22

Salvador Dali · Accepted Answer · 2015-12-06 03:08:13Z

4

What you have been told is correct. The algorithm runs in O(nlog(n)). The third line: for(j=1; j<= n; j*=3) runs in O(log3(n)) because you multiply by 3 each time. To see it more clearly solve the problem: how many times you need to multiply 1 by 3 to get n. Or 3^x = n. The solution is x = log3(n)

answered Dec 6, 2015 at 3:08

Salvador Dali

224k151 gold badges726 silver badges766 bronze badges

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

3 Comments

user3707125 Over a year ago

Please stop writing constants inside Big O notation, it describes the speed of function's growth in relation to input parameter(s), not estimated execution time.

Salvador Dali Over a year ago

@user3707125 where do you see constants? I wrote about log3 because the OP explicitly asked where log3 came from.

user3707125 Over a year ago

here: "runs in O(log3(n))", it would be more correct to say "runs approximately log3(n) times, which results in asymptotic complexity of O(log(n))".

achin · Accepted Answer · 2015-12-06 03:13:33Z

1

Yes. Algo runs in nlog(n) times where log is base 3.

The easiest way to calculate complexity is to calculate number of operations done.

The outer for loop runs n times. And let's calculate how many times each inner for loop runs for each n. So for n=1,2, inner for loop runs 1 times. For n=3,4,5,6,7,8 inner for loop runs 2 times. And so on...

That means that the inner for loop runs in logarithmic time (log(n)) for each n.

So n*log(n) will be total complexity.

answered Dec 6, 2015 at 3:13

achin

1691 silver badge8 bronze badges

Comments

Jorgel · Accepted Answer · 2015-12-06 03:03:36Z

0

On the second loop you have j *= 3, that means you can divide n by 3 log3(n) times. That gives you the O(logn) complexity.
Since your first loop has a O(n) you have O(nlogn) in the end

answered Dec 6, 2015 at 3:03

Jorgel

9303 gold badges14 silver badges30 bronze badges

Collectives™ on Stack Overflow

Complexity of An Algorithm(Nested loops)

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related