Time complexity of loop multiplying the value by two or three

Question

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++;

Answer 1

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.

Answer 2

The answer is N×log₃N.

To see why, you need to figure out why the answer to the original problem is N×log₂N. 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, 2^k > N. Now apply logarithm to both sides of the expression (the definition of logarithm can be found here) to see that k > log₂N.

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 log₃ yields the answer to the problem that you are solving.