-3
$\begingroup$

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

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

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Why the case n=-1 ? $\endgroup$
    – user16034
    Jan 24, 2023 at 7:56
  • 1
    $\begingroup$ while y ≠ 0. Never true if you start with y = -1. $\endgroup$
    – gnasher729
    Jan 24, 2023 at 11:53
  • 1
    $\begingroup$ Of course, but how is that useful to complexity analysis ? $\endgroup$
    – user16034
    Jan 24, 2023 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, 2023 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$
    – user16034
    Jan 25, 2023 at 14:02
0
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.