0
$\begingroup$

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:

  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.

$\endgroup$

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.