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)$

**Questions:**

- Is the solution in terms of $ k$ correct?
- 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.*