# What is the time complexity of $\sum_{i=0}^{\frac{n}{k}} p_i\cdot 2^{ik}$ if $p$ is a binary number?

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 $(*)$?

• @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$? – Yos Dec 10 '17 at 14:31
• 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. – gnasher729 Dec 10 '17 at 14:34
• And large numbers will be stored in multiple words, so shifting a small number by i bits will be done in constant time. – 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.
• 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)$? – Yos Dec 10 '17 at 18:56