-1

Got code for time complexity analysis in practice test:

for i ​in​ 0..n-1:
    ​for​ j ​in​ 0..i:

The answer wrote the complexity for this as O(n^2) with the explanation that both loops have complexity O(n). I am confused by why this isn't O(n!), given that the inner loop will run first 0 times, then 1, 2, 3 and so on until n-1 times.

Catfish
  • 65
  • 9
  • How are you getting `n!` out of that? The factorial is the *product* of the first `n` numbers, not their sum... – jasonharper Jan 04 '21 at 14:57
  • Does this answer your question? [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Mo B. Jan 05 '21 at 19:48

1 Answers1

1

The inner loop will run O(Sigma(n)) times or O(n^2).

If

  • the first iteration runs 0 times and the last one n-1 times,
  • the second iteration runs 1 time and the next to last n-2 times,
  • the third iteration to 2 times an the second from last n-3 times, etc

then they average out to to (n-1) that happens (n/2) times - or O(n^2)

Dr Dave
  • 550
  • 1
  • 6
  • 22