# 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, 2023 at 20:13
• No. This is very specific and follows the exact format for asking questions. Jan 23, 2023 at 12:41
• Do you know the definition of Θ ? If yes, do you understand it ?
– user16034
Jan 23, 2023 at 15:31
• BTW, the downvotes are because you don't show any attempt. Jan 23, 2023 at 16:30
• Something has gone wrong near $c2$ & $c3$. can't attach a PDF You can use $L^AT_EX$. Jan 24, 2023 at 8:39

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

• Why the case n=-1 ?
– user16034
Jan 24, 2023 at 7:56
• while y ≠ 0. Never true if you start with y = -1. Jan 24, 2023 at 11:53
• Of course, but how is that useful to complexity analysis ?
– user16034
Jan 24, 2023 at 13:07
• It means the complexity analysis is totally off. There are instances where the execution doesn’t even end. Jan 25, 2023 at 13:34
• Sorry, my bad, I did not consider that the OP said |y|=n. In fact, with this condition, T(n) is always infinite !
– user16034
Jan 25, 2023 at 14:02

line 1: c1 line 2: n line 3: c2 line 4: c3 line 5: c4

T(n) = c1 + n + c2n + c3n + c4n T(n) = theta(n)