CODEWITHSUNDEEP
c++algorithmtime-complexity
Wasim Thabraze
Wasim Thabraze

Reputation: 810

Time complexity of loop multiplying the value by two or three

I found the below for-loop in an SO question.

I found that the time complexity is O(n log n).

How would I find the time complexity if we change k *= 2 to k *= 3?

// 'int n' is defined somewhere
int var = 0;
for (int k = 1; k <= n; k *= 2)
   for (int j = 1; j <= n; j++)
      var++;

Upvotes: 3

Views: 6339

Answers (3)

Bernhard Barker
Bernhard Barker

Reputation: 55619

The time complexity would still be O(n log n).

For k *= 2, the log would be base 2.

For k *= 3, the log would be base 3.

But change in the base of log only affects the result by a constant factor (this can be derived from the fact that logba = logca / logcb, for any base c), which is ignored in big-O notation, thus they have the same time complexity.

Where do we get log2n from anyway?

Well, the values of k goes like this:

1, 2, 4, 8, 16, ..., 2m  for some m, where 2m <= n < 2m+1
= 20 + 21 + 22 + ... + 2m

And of course there are just m+1 (0 to m) terms above, so the loop runs m+1 times.

Now if we can use some basic logarithms to get m in terms of n:

2m = c.n   for some constant c, where 1 <= c < 2
log22m = log2(c.n)
m log22 = log2(c.n)
m.1 = log2c + log2n
m = O(log2c + log2n)
  = O(log2n)               // constant terms can be ignored

We can also follow the exact same approach as above for k *= 3 by just replacing 2 by 3.

Upvotes: 10

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

You can proceed formally and methodically using Sigma notation:

enter image description here

Check the last slides of this document.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726809

The answer is N×log3N.

To see why, you need to figure out why the answer to the original problem is N×log2N. How many times (let's call it k) will it execute? It will execute as many times as needed to multiply 2 by itself so that the result would exceed N. In other words, 2k > N. Now apply logarithm to both sides of the expression (the definition of logarithm can be found here) to see that k > log2N.

The reason that we used 2 as the base of the logarithm is that the base of the exponent on the left was 2. It is easy to see that if the base of exponen is 3, applying log3 yields the answer to the problem that you are solving.

Upvotes: 3

Related Questions