Let $p$ be a number represented in binary of length $n$. We'll divide $p$ into $\frac{n}{k}$ parts, each of length $k$ (let each part be $p_i$, $0 \le i\le \frac{n}{k}$) where $k=\lg n$. Now we want to represent $p$ as a sum: $$ \sum_{i=0}^{\frac{n}{k}} p_i\cdot 2^{ik} \qquad(*) $$

I know that multiplying a number in binary by $2^{ik}$ is the same as shifting $i$ bits to the left which should be an $\Theta(1)$ operation in real life but theoretically this could be a $\Theta(n)$ operation because we may have to shift up to $n$ bits to the left. So the sum above becomes $\Theta(n^2)$.

Is there a faster way to perform the sum operation $(*)$?

  • $\begingroup$ @gnasher729 unfortunately these are the conditions for the problem. If $n \mod k \neq 0$ then we can just add zeroes I suppose. Why isn't the sum equal to $p$? $\endgroup$ – Yos Dec 10 '17 at 14:31
  • 1
    $\begingroup$ I recommend you figure out exactly what your problem is. I would bet that something has been misunderstood. If it is homework, and you understood the homework correctly, then I would bet that your teacher misunderstood something. $\endgroup$ – gnasher729 Dec 10 '17 at 14:34
  • $\begingroup$ And large numbers will be stored in multiple words, so shifting a small number by i bits will be done in constant time. $\endgroup$ – gnasher729 Dec 10 '17 at 14:35

The running time to compute the sum is $O(n)$ bit operations. You just concatenate $p_1,p_2,\dots,p_{n/k}$ and you've got your answer.

  • $\begingroup$ If course! I should've thought about this. Just for the sake of interest if I were to shift by $ik$ bits would the running time be $\Theta(n^2)$? $\endgroup$ – Yos Dec 10 '17 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.