Time complexity of an iterative function related to bits

Question

I am wondering about correct answer to this task from a test earlier today:

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.

Answer 1

One of the area where there is often a lack of rigor in discussions of time complexity is failing to be precise about what the complexity is in terms of. Here, you are given three variables: $a$, $k$, and $n$. The problem states that "The dominant operation is a compare operation performed in line 6", which implies that the complexity of such lines as z := z * z should be ignored, and thus that the complexity should not be given in terms of $a$. While $k$ is the other parameter given for the function, the problem statement does go out of its way to state that $k$ has $n$ bits. Furthermore, it is traditional to give complexity classes in terms of functions of $n$.Those two facts point to the instructor expecting students to give their results in terms of $n$.

On the other hand, the question asks "Describe shortly the value of k when the worst case occurs." Besides the fact that this is worded in terms in $k$, there is the fact that when the complexity is given in terms of $n$, it is always $n$, making the question a bit trivial. But when it is given in terms of $k$, it varies.

You give the worst case as being $\lfloor \log_2 k \rfloor$, but that's not right. Remember that numbers start with a units digit, or $base^0$. Since we're starting at zero, the number of digits is one more than power of the most significant digit. For instance, for 15, we have the 8, or 2^3, place, the 2^2 place, the 2^1 place, and the 2^0, for a total of four digits, even though the most significant digit is 2^3. So the formula is $1+\lfloor log_2 k \rfloor$. Also, if you're looking for the worst case, we can get rid of the floor function; the worst case is when $k$ is a power of $2$, in which case we're not rounding down at all. So we can give the worst case as just $1+\log_2 k$. The best case asymptotically approaches $\log_2 k$ (for $2^n-1$, $1+\lfloor log_2 k \rfloor$ is only slightly more than $\log_2 k$). Taking a simple average of these gives $0.5 + \log_2 k$, but since the numbers will be more clustered around the worst case scenarios, dpending on how one calculates the "average", the exact number could be a bit higher. My guess would be $1-\frac 1 e + \log_2 k$.

$k=0$ is indeed a special case, as $\log 0$ is not a real number (there are number systems in which it can be given as $-\infty$).