1
$\begingroup$

I want to classify the runtime of this function in big O notation. This function is multiplying two whole numbers and checks the in binary digits of the multiplicand. And adding the multiplier to the product a specific number of times if the bit is '1', dependent on the weigth of that bit.

I'm trying to figure out the classifcation of the for-loop. Since the while-loop will go through all bits of the multiplicand the while-loop will probably have a runtime of $O(n)$ whereas $n = \#digits$. The inner loop will execute $2^0, 2^1, 2^2, 2^3, 2^4...=1, 2, 4, 8, 16,...$ if the bit will be a '1'. So in total the for-loop will execute $\sum_{i=0}^{n-1}2^i$ steps, in the worst-case (if all bits are ones).

My question is, how do I write this for-loop in big O notation?

def mul(multiplier,multiplicand):
    product = 0
    pot = 1                             # power of two
    while (multiplicand > 0):
        q = divtwo(multiplicand)
        q1 = (q + q)
        if (q1 != multiplicand):        # is odd => bit 1
            for i in range(0,pot):
                product = (product + multiplier)
        multiplicand = q
        pot = (pot + pot)
    return product

P.S.: I'm not allowed to use "/" or "*". Only "+" and "-".

$\endgroup$
  • $\begingroup$ I'm not sure what you're asking. Don't you already have the answer, except that you just need to notice that $1, 2, 4, \dots, 2^{n-1}$ is a geometric progression and look up the form of the sum of the first $k$ terms of such a progression to let you rewrite $\sum_{i=0}^{n-1}2^i$ in a nicer form? $\endgroup$ – David Richerby May 6 '16 at 0:09
  • 4
    $\begingroup$ And, by the way, you don't "write this for-loop in big O notation", just as you don't "write this car in miles per hour notation". $\endgroup$ – David Richerby May 6 '16 at 0:10
  • $\begingroup$ Oh. Can't believe how I could not see that. Thanks :) $\endgroup$ – JumbleGee May 6 '16 at 0:58
  • 1
    $\begingroup$ Do you now have enough to answer your own question? If so, feel free to write an answer now! $\endgroup$ – D.W. May 6 '16 at 4:55
  • $\begingroup$ Our reference question explains in detail how to do this; there are also many examples about algorithm-analysis+loops. Hint: proceed inside-out, not outside-in. $\endgroup$ – Raphael May 6 '16 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.