# How to determine big O of a variable loop

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 "-".

• 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? – David Richerby May 6 '16 at 0:09
• 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". – David Richerby May 6 '16 at 0:10
• Oh. Can't believe how I could not see that. Thanks :) – JumbleGee May 6 '16 at 0:58
• Do you now have enough to answer your own question? If so, feel free to write an answer now! – D.W. May 6 '16 at 4:55
• 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. – Raphael May 6 '16 at 6:14