8

What's the correct big O notation for an algorithm that runs in triangular time? Here's an example:

func(x):
  for i in 0..x
    for j in 0..i
      do_something(i, j)

My first instinct is O(n²), but I'm not entirely sure.

zildjohn01
  • 11,339
  • 6
  • 52
  • 58

6 Answers6

19

Yes, N*(N+1)/2, when you drop the constants and lower-order terms, leaves you with N-squared.

Brian
  • 117,631
  • 17
  • 236
  • 300
1

Yeah, O(n^2) is definitly correct. If I recall correctly, O is anyway always an upper bound, so O(n^3) should IMO also be correct, as would O(n^n) or whatever. However O(n^2) seems to be the most tight one that is easily deductable.

Janick Bernet
  • 20,544
  • 2
  • 29
  • 55
1

The computation time increases by the factor of N*(N + 1)/2 for this code. This is essentially O(N^2).

rajeshnair
  • 1,587
  • 16
  • 32
0

when the input increases from N to 2N then running time of your algorithm will increase from t to 4t

thus running time is proportional to the square of the input size

so algorithm is O( n^2 )

Serdar Sanli
  • 1,064
  • 1
  • 11
  • 20
-1

If you think about it mathematically, the area of the triangle you are computing is ((n+1)^2)/2. This is therefore the computational time: O(((n+1)^2)/2)

reece
  • 7,945
  • 1
  • 26
  • 28
-4

O(!n) handles cases for a factorial computation (triangular time).

It can also be represented as O(n^2) to me this seems to be a bit misleading as the amount being executed is always going to be half as much as O(n^2) would perform.

Paul
  • 1
  • 1
  • By definition, `O(0.5 * n^2) == O(n^2)` (an equality that holds for any non-zero constant factor, in fact), so from a strictly theoretical perspective this is not misleading. :-) – Gijs Nov 04 '12 at 23:46
  • 3
    -1. A [Factorial](http://en.wikipedia.org/wiki/Factorial) is not the same as a [triangular number](http://en.wikipedia.org/wiki/Triangular_number). – gilly3 Feb 06 '13 at 19:33
  • Factorial is `product({1…n})`, triangle number is `sum({1…n}) ≈ n²`. – ctrl-alt-delor Dec 12 '21 at 15:56