Tricky time complexity

Question

I've gotten pretty good at figuring out time complexity, but am still confused about how to determine exponential time algorithms. The algorithm below has a worst case running time O(k^n). How did they get this value? The first for-loop takes n time, the second for-loop takes k time, and the third for-loop with q is confusing. If the running time is n * k * q-something, how did they get O(k^n)?

int exp(k, n) {
    power = 1
    for i = 1 to n {
        newpower = 0
        for j = 1 to k {
            for q = 1 to power {
                newpower++
            }  
        }
        power = newpower
    }
    return (power)
}

Answer 1

O(k^n) seems correct to me.

The j-and q-loop has total k * power iterations. But power is updated exponentially each i-loop iteration.

• When i=1, j-and q-loop has k * 1 iterations.
• When i=2, j-and q-loop has k * k iterations.
• When i=3, j-and q-loop has k * (k*k) iterations.
• When i=m, j-and q-loop has k * (k^(m-1)) iterations.

k*(k^(m-1)) is just k^m, where 1 <= m <= n. So for n iterations, the sum of all iterations is asymptotically O(k^n).

Answer 2

After the third loop appeard, the complexity of O(k^n) makes sense.

First you have to see that the algorithm computes k^n:

• The q-loop adds the current power to newpower
• The k-loop runs the q-loop k times, so this compute k * power
• this is executet n times by the i-loop

So you get k* .... k*(k*(k*1)) (n-times) = k^n

Now we know that the algorithm compute k^n and it does this only by adding 1's, so he need to add k^n 1's, so the complexity is O(k^n) (Θ(k^n) exactly)

Answer 3

The complexity of the algorithm you have given is not O(k^n). The complexity is just O(nk). The algorithm evaluates nk.

Answer 4

To solve these trickier problems, you have to meticulously count the number of instructions that are being executed, and this is not always easy (can require higher levels of math).

In this problem, let's try to count the number of times newpower++ happens (i.e. the number of loops in the inner-most loop), and lets look at it in chunks of the k loop. In the first run, there are k chunks of 1 run each:

1 1 1 1 ...
= looped 1*k times = k times

and then power = k. Then we have k chunks of k: k k k k ...
= looped k*k times = k^2 times

continue this pattern and you will see that the number of times newpower++ executes is:
k + k^2 + k^3 + ... k^n times.

However the k^n term dominates the rest, so you are left with O(k^n).

Answer 5

This

       for q = 1 to power {
            newpower++
       }  

can be reduced to

       newpower += power;

And this

    newpower = 0
    for j = 1 to k {
        for q = 1 to power {
            newpower++
        }  
    }
    power = newpower

to

   power *= k;

So it actually calculates k^n by repeatedly incrementing. This is O(k^n).