<p>Your algorithm has a time complexity of $O(n \log n)$. </p>

<p>Your algorithm uses $O(\log M)$ intermediate words each of size $O(\log \log M)$. Thus, the algorithm writes up to $O(\log M \log \log M)$ bits, taking $O(\log M \log \log M)$ elementary bit steps. Since the complexity is measured based on the input size, which is $\log M$ in your case, it has a complexity of $O(n \log n)$ [to multiply two words represented by $n$ bits].</p>

<p>Further note that since $O(.)$ only gives an upper bound on the asymptotic worst-case runtime, it is possible that your algorithm is actually faster, ie, the bound was not tight. For example, the algorithm could use just 1 intermediary word of size 1, which would make the algorithm be in $O(1)$.</p>

CC BY-SA 3.0
2011-07-22T11:14:29.663Z
How about using only variable portion of the $O(\log{\log{M}})$ bits at each step. Would that also lead to reduction in complexity of the complexity is still on the absolute word size?
v s
CC BY-SA 3.0
2011-07-22T16:38:38.823Z
I am not sure if I understand your last comment.
danielzinn
CC BY-SA 3.0
2011-07-22T17:09:25.813Z
say if $M=2^{2^{k}}$. Then, it may be possible all the intermediate words of size $k$ do not use all the bits. If we know, the pattern ahead, we could in run-time change the word sizes we work on.
v s
CC BY-SA 3.0
2011-07-22T17:13:27.867Z
"....reduction in complexity OR does the complexity is still based on the absolute word size?"
v s
CC BY-SA 3.0
2011-07-22T17:29:17.770Z
Sure. You can write a different algorithm that only works on your restricted input, and just rejects input not of the restricted form. This different algorithm might have a different complexity, of course. However, complexity is generally meant to be worst-case (unless stated otherwise). So, considering your original algorithm: even though it might have good cases (where it is faster), in worst case it might use up $O(\log M)$ many words of size up to $O(\log \log M)$ bits.
danielzinn
CC BY-SA 3.0
2011-07-22T05:05:00.273Z
2011-07-22T05:53:47.863Z
2011-07-22T05:53:47.863Z
danielzinn
<p>I have a simple technical question on multiplication of finite bit words. Say the number of bits of words that need to be multiplied is $O(\log{M})$ and say an hypothetical algorithm uses $O(\log{M})$ intermediate words of size $O(\log\log{M})$ bits (doing simple addition and modulo-$2$ operations for $O(\log{M})$ times on these $O(\log\log{M})$ bit words) and producing the final output of $O(\log{M})$ bits, would that be an $O(\log{M})$ bit/time complexity or an $O(\log{M}\log\log{M})$ bit/time complexity algorithm? I looked on literature and I could not identify the exact notion/relation bit time and bit space complexity of such algorithms. Atleast it was not clear to me.</p>

<cc.complexity-theory><terminology>
Data representation and bit/time complexity
v s
# Data representation and bit/time complexity

(Asked by: username_0 on 2011-07-20)

I have a simple technical question on multiplication of finite bit words. Say the number of bits of words that need to be multiplied is $O(\log{M})$ and say an hypothetical algorithm uses $O(\log{M})$ intermediate words of size $O(\log\log{M})$ bits (doing simple addition and modulo-$2$ operations for $O(\log{M})$ times on these $O(\log\log{M})$ bit words) and producing the final output of $O(\log{M})$ bits, would that be an $O(\log{M})$ bit/time complexity or an $O(\log{M}\log\log{M})$ bit/time complexity algorithm? I looked on literature and I could not identify the exact notion/relation bit time and bit space complexity of such algorithms. Atleast it was not clear to me.

**Tags:** cc.complexity-theory, terminology


---

## 1 answers

### Answer by username_1 on 2011-07-22. Score: 1 | Accepted answer

Your algorithm has a time complexity of $O(n \log n)$.

Your algorithm uses $O(\log M)$ intermediate words each of size $O(\log \log M)$. Thus, the algorithm writes up to $O(\log M \log \log M)$ bits, taking $O(\log M \log \log M)$ elementary bit steps. Since the complexity is measured based on the input size, which is $\log M$ in your case, it has a complexity of $O(n \log n)$ [to multiply two words represented by $n$ bits].

Further note that since $O(.)$ only gives an upper bound on the asymptotic worst-case runtime, it is possible that your algorithm is actually faster, ie, the bound was not tight. For example, the algorithm could use just 1 intermediary word of size 1, which would make the algorithm be in $O(1)$.

> **Comments:**
> **username_0**: How about using only variable portion of the $O(\log{\log{M}})$ bits at each step. Would that also lead to reduction in complexity of the complexity is still on the absolute word size?  
> **username_1**: I am not sure if I understand your last comment.  
> **username_0**: say if $M=2^{2^{k}}$. Then, it may be possible all the intermediate words of size $k$ do not use all the bits. If we know, the pattern ahead, we could in run-time change the word sizes we work on.  
> **username_0**: "....reduction in complexity OR does the complexity is still based on the absolute word size?"  
> **username_1**: Sure. You can write a different algorithm that only works on your restricted input, and just rejects input not of the restricted form. This different algorithm might have a different complexity, of course. However, complexity is generally meant to be worst-case (unless stated otherwise). So, considering your original algorithm: even though it might have good cases (where it is faster), in worst case it might use up $O(\log M)$ many words of size up to $O(\log \log M)$ bits.  

---

