1
$\begingroup$

The efficiency of the algorithm dolt can be expressed as O(n)=n^3.Calculate the efficiency of the following program segment exactly and by using the big-O notation.

for (i=1; i <= n+1; i++)
    for (j=1; j < n; i++)
        dolt (...)

The second loop is nested but I'm not sure how to format it on the website.

I'm trying to find out if I'm on the right track. My answer was: $$n\cdot n\cdot (n^3)= n^5 = O(n^5)$$

$\endgroup$
6
  • 5
    $\begingroup$ Sorry, but $O(n)=n^3$ is some very strange and probably wrong notation. $\endgroup$
    – Thomas Andrews
    Commented Sep 2, 2014 at 18:41
  • $\begingroup$ Is it? O(n)=n^3 is how it's written in the question exactly. $\endgroup$
    – Owen
    Commented Sep 2, 2014 at 18:47
  • $\begingroup$ Then your instructor and/or book is using the notation very strangely. $\endgroup$
    – Thomas Andrews
    Commented Sep 2, 2014 at 18:52
  • $\begingroup$ In the inner loop, shouldn't it be j++ instead of i++? $\endgroup$
    – user137481
    Commented Sep 2, 2014 at 18:59
  • 1
    $\begingroup$ Rather perversely, O in O(n)=n^3 is probably not Big-O. $\endgroup$
    – Did
    Commented Sep 2, 2014 at 18:59

1 Answer 1

Reset to default
1
$\begingroup$

Since,the second "for" is nested, the second "for" is implemented $(n+1-1+1) \cdot (n-1+1)=(n+1) \cdot n$ times.

The cost of the algorithm dolt is expressed as $g(n)=O(n^3)$,so $\exists c>0 \text{ and} n_0 \geq 1$ such that $\forall n \geq n_0$: $g(n) \leq c n^3$

Since,the algorithm "dolt" is also nested, $\text{ cost } \leq Cn(n+1)n^3=O(n^5)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .