0
$\begingroup$

I need to compute the time and space complexity in Big O notation for this algorithm I constructed for binary multiplication.

mul(a, b) = 

 - 0 if a = 0 or b = 0
 - (b + p) if lowest(a) != 0
 - p if lowest(a) = 0

where

  • p = join(mul(higher(a), b), 0)

  • lowest(a) returns the lowest order bit of a binary numeral a

e.g. lowest(1001101) = 1

  • higher(a) returns the binary numeral excluding the lowest order bit of binary numeral a

e.g. higher(1001101) = 100110

  • join(a, b) appends bit b at the end of binary numeral a

e.g. join(1101, 1) = 11011

$\endgroup$
3
  • $\begingroup$ cs.stackexchange.com/q/23593/755 $\endgroup$
    – D.W.
    Jan 3 at 9:47
  • $\begingroup$ I went through that but unfortunately I drew a blank. I'm quite new to algorithm analysis and I really am lost on how complexity is calculated. @D.W. $\endgroup$ Jan 3 at 11:19
  • 1
    $\begingroup$ There are lots of textbooks that contain material on how to approach that. What self-study have you done? What are your current attempts? Right now your question could be viewed as "please do this work task for me", which isn't really the purpose of this site. Part of our mission here is to build up an archive of high-quality questions and answers that will be useful to others in the future. Can you articulate a question that will be useful to others even if they aren't wondering about exactly the same algorithm you are? $\endgroup$
    – D.W.
    Jan 3 at 21:01
0
$\begingroup$

It's a recursive algorithm. Each time you call mul (through the use of p) you decrease the number of bits of 'a' by one. So the time complexity is the number of bit in 'a'. And since the number of bits equals the log of the value of 'a', so the recursion depth is Log(a).

In each step of the recursion you might perform an add operation of Max(Log(b),Log(a)) bits.

So the time complexity is O(Log(a)*Max(Log(b), Log(a)))

If a and b are roughly the same size you will get O(Log(a)^2)

$\endgroup$

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.