Calculating tilde-complexity of for-loop with cubic index

Question

Say I have following algorithm:

for(int i = 1; i < N; i *= 3) {
   sum++
}

I need to calculate the complexity using tilde-notation, which basically means that I have to find a tilde-function so that when I divide the complexity of the algorithm by this tilde-function, the limit in infinity has to be 1.

I don't think there's any need to calculate the exact complexity, we can ignore the constants and then we have a tilde-complexity.

By looking at the growth off the index, I assume that this algorithm is

~ log N 

But rather than having a binary logarithmic function, the base in this case is 3. Does this matter for the exact notation? Is the order of growth exactly the same and thus can we ignore the base when using Tilde-notation? Do I approach this correctly?

Answer 1

You are right, the for loop executes ceil(log_3 N) times, where log_3 N denotes the base-3 logarithm of N.

No, you cannot ignore the base when using the tilde notation.

Here's how we can derive the time complexity. We will assume that each iteration of the for loop costs C, for some constant C>0.

Let T(N) denote the number of executions of the for-loop. Since at j-th iteration the value of i is 3^j, it follows that the number of iterations that we make is the smallest j for which 3^j >= N. Taking base-3 logarithms of both sides we get j >= log_3 N. Because j is an integer, j = ceil(log_3 N). Thus T(N) ~ ceil(log_3 N).

Let S(N) denote the time complexity of the for-loop. The "total" time complexity is thus C * T(N), because the cost of each of T(N) iterations is C, which in tilde notation we can write as S(N) ~ C * ceil*(log_3 N).