0

The efficiency of the algorithm doIt can be expressed as O(n) = n^3. Calculate the efficiency of the following program segment exactly. Then calculate the efficiency using the big-O notation. Show calculations.

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

Thanks in advance.

Anders Olsson
  • 1
  • What do **you** think the complexity is? – amit Sep 02 '14 at 15:23
  • possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – David Eisenstat Sep 02 '14 at 15:25
  • I don't know what it is exactly, but I think the big-O notation would be n^4. – Anders Olsson Sep 02 '14 at 15:31
  • 1
    Well the outer (`i`) loop runs `n+1` times, and the inner (`j`) loop runs `n-1` times for each iteration of the outer loop - the product of those two counts is `n^2-1`, which is `O(n^2)`. If the function being called is `O(n^3)`, and you're running it `O(n^2)` times, it would seem to me the total complexity would be `O(n^3 * n^2)` or `O(n^5)`... – twalberg Sep 02 '14 at 16:32

1 Answers1

0

There are two for loops each iterating (almost) n times. So O(n^2) for them.

A method of O(n^3) is called (almost) n^2 times, then you will have n^2 * n^3 which will eventually get you to :

O(n^5)

rahman
  • 4,820
  • 16
  • 52
  • 86