# Data representation and bit/time complexity

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.

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)$.
• 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 Jul 22 '11 at 11:14
• 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 Jul 22 '11 at 17:09
• 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 Jul 22 '11 at 17:29