# Question about efficiency of an algorithm (Big-O)

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

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

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