# Time complexity of simple function related to bits

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:

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.