I am wondering about correct answer to this task from a yesterday's test:

A function Pow which calculates $y = a^k$ is given, where $k$ is an integer of length $n$ bits:

function Pow(a, k)     { k >= 0 }
    z := a;
    y := 1;
    m := k;
    while m != 0 do
        if m mod 2 = 1 then
            y := y * z;
        end if
        m := m div 2;
        z := z * z;
    end while
    return y;
end function

Calculate the worst case time complexity and the average time complexity of this function. The dominant operation is a compare operation performed in line 6. Describe shortly the value of $k$ when the worst case occurs.

So, I believe the number of comparisons is dependant on length of $k$ in terms of its bits.

Let $k = 0$: (binary $0$ too, which is $1$ bit):

$\Rightarrow 0$ comparisons

Let $k = 1$: (binary $1$ too, which is $1$ bit):

$\Rightarrow 1$ comparison

Let $k = 8$: (binary $1000$ which is $4$ bits)

$\Rightarrow 4$ comparisons

Let $k = 15$: (binary $1111$ which is $4$ bits)

$\Rightarrow 4$ comparisons

Let $k = 16$: (binary $10000$ which is $5$ bits)

$\Rightarrow 5$ comparisons

I think a pattern can be seen.

Any number from the set $\{2^h, 2^h + 1, \cdots, 2^{h+1} - 2, 2^{h+1} - 1 \} \quad \land \quad h > 0 \quad$, is $h + 1$ bits long and hence $h + 1$ comparison.

So I'd believe $T_{avg}(n) = T_{worst}(n) = n \in O(n)$

But $n$ is number of bits of $k$ number. Function takes $k$ as a parameter, not $n$. So my solution is not the one that's desired, I think.

In terms of $k$ I think it would look like that:

$T_{worst}(k) = \lfloor log_{2}(2k) \rfloor \in O(\log k)$

$T_{avg}(k) = \lfloor log_{2}(2k)\rfloor \in O(\log k)$


  1. Is the solution in terms of $k$ correct?
  2. The solution in terms of $n$: how would you grade that, personally? Knowing the task's description from the above.

I have posted similiar thread on math stackexchange, but would like to get more opinions on this from CS experts themselves.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.