0

Another Big O question, yet I can't wrap my head around it:

for (int i = 0; i < n; i++)
    for (int j = 0; j < n * n; j++)
        for (int k = 0; k < j; k++)
            //do sth

My thought: The outer loop is O(n). The middle is O(n^2). However, the inner depends on the middle, so for each j, k is gonna run 1+2+3+...+n = [n^2(n^2+1)]/2 which is the same as O(n^4).
So instead the middle runs about O(n^2), it actually runs O(n^4). Which would result in O(n^5). Is that correct?

Phineas
  • 159
  • 2
  • 10
  • 1
    Yes, that's right. Also, this is roughly answered by https://stackoverflow.com/questions/362059/what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop – Wyck Oct 05 '20 at 13:42

1 Answers1

0

The total amount of loop iterations is Θ(n5).

1

Eloy Pérez Torres
  • 1,050
  • 4
  • 14