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.
