# How can we analyze the procedure Product: multiply two n-bits binary numbers x and y?

I am trying to analyze the algorithm Product: multiply two n-bits binary numbers x and y.

function Product(x, y);
1. prod = 0;
2. while y not eq 0
3.     y = y -1;
4.     prod = prod + x;
return prod;


Assume: n = |x| = |y|
Give the worst case time T(n) function for algorithm Product.
Express T(n) in terms of a big-Θ function in n.
Analysis:

T(n) = c1 + n + c2 + c3

I would appreciate it if someone could explain how to use big-Θ to express T(n).

• Does this answer your question? Is there a system behind the magic of algorithm analysis? Jan 22 at 20:13
• No. This is very specific and follows the exact format for asking questions. Jan 23 at 12:41
• Do you know the definition of Θ ? If yes, do you understand it ? Jan 23 at 15:31
• BTW, the downvotes are because you don't show any attempt. Jan 23 at 16:30
• Something has gone wrong near $c2$ & $c3$. can't attach a PDF You can use $L^AT_EX$. Jan 24 at 8:39

Answer these two questions: How many iterations when n = 1 billion? How many iterations when n = -1?