CODEWITHSUNDEEP
algorithmmathtime-complexitybig-o
Maya
Maya

Reputation: 85

Determining the big-O run-times of these different loops?

Determining the big-O run-times of these different loops?

for i = 1 to n {
  ...
  for  j = 1 to 2*i {
    ...
    k = j;
    while (k>=0) {
      ...
      k = k-1;
    }
  }
}

I found the answer to be O(n^3) since three loops are nested inside each other, Is my answer correct?

Upvotes: 0

Views: 78

Answers (1)

Rory Daulton
Rory Daulton

Reputation: 22544

That is correct as a heuristic, but such heuristics can lead you astray. It is possible to find the exact formula for the number of inner loops.

For each j, k runs from j down to 0 inclusive, so the inner loop is run j+1 times.

For each i, j runs from 1 through 2*i, so the inner loop is run 1+1 and 2+1 times for i=1, then also 3+1 and 4+1 times for i=2, and so on. I hope you can see that for each i the inner loop is run one less than the (2i+1)'th triangular number. The n'th triangular number is n(n+1)/2, so for each i we get a count of

(2i+1)(2i+1+1)/2 - 1

which simplifies to

2 * i**2 + 3 * i

For each n, i runs from 1 through n, so we just sum that last expression from 1 through n. That gives us twice the sum of the first n square numbers plus thrice the nth triangular number. The formula for the sum of the first n square numbers is

n**3/3 + n**2/2 + n/6

So we simplify

2*(n**3/3 + n**2/2 + n/6) + 3*(n*(n+1)/2)

and we get

2/3 * n**3 + 5/2 * n**2 + 11/6 * n

That obviously is O(n**3), so your heuristic was correct.

I checked that final expression with some simple Python code.

Upvotes: 3

Related Questions