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)$.

  • $\begingroup$ 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? $\endgroup$ – v s Jul 22 '11 at 11:14
  • $\begingroup$ I am not sure if I understand your last comment. $\endgroup$ – danielzinn Jul 22 '11 at 16:38
  • $\begingroup$ 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. $\endgroup$ – v s Jul 22 '11 at 17:09
  • $\begingroup$ "....reduction in complexity OR does the complexity is still based on the absolute word size?" $\endgroup$ – v s Jul 22 '11 at 17:13
  • $\begingroup$ 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. $\endgroup$ – danielzinn Jul 22 '11 at 17:29

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.