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

Question

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? — Nathaniel, Jan 22 at 20:13
No. This is very specific and follows the exact format for asking questions. — Evan Gertis, Jan 23 at 12:41
Do you know the definition of Θ ? If yes, do you understand it ? — Yves Daoust, Jan 23 at 15:31
Something has gone wrong near $c2$ & $c3$. can't attach a PDF You can use $L^AT_EX$. — greybeard, Jan 24 at 8:39

gnasher729 · Accepted Answer · 2023-01-24 07:19:45Z

0

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

With that you should have no problem answering your question.

answered Jan 24 at 7:19

gnasher729

27k30 silver badges46 bronze badges

$\begingroup$ Why the case n=-1 ? $\endgroup$
– Yves Daoust
Jan 24 at 7:56
1

$\begingroup$ while y ≠ 0. Never true if you start with y = -1. $\endgroup$
– gnasher729
Jan 24 at 11:53
1

$\begingroup$ Of course, but how is that useful to complexity analysis ? $\endgroup$
– Yves Daoust
Jan 24 at 13:07
$\begingroup$ It means the complexity analysis is totally off. There are instances where the execution doesn’t even end. $\endgroup$
– gnasher729
Jan 25 at 13:34
$\begingroup$ Sorry, my bad, I did not consider that the OP said |y|=n. In fact, with this condition, T(n) is always infinite ! $\endgroup$
– Yves Daoust
Jan 25 at 14:02

Add a comment |

Evan Gertis · Accepted Answer · 2023-01-27 14:02:21Z

0

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)

answered Jan 27 at 13:37

Evan Gertis

1054 bronze badges

Add a comment |

2 Answers 2