Geek Answers Handbook

Big O designation for triangular numbers?

What is the correct big O notation for an algorithm that works in triangular time? Here is an example:

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

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

+5
source share
6 answers

Yes, N * (N + 1) / 2, when you drop constants and low-order terms, you get an N-square.

+12
source

Yes, O(n^2)definitely right. If I remember correctly, O is always the upper bound anyway, so O(n^3)IMO should also be correct, like O(n^n)or something else. However, O(n^2)it seems the most difficult that is easily subtracted.

+1
source

, , , ((n+1)^2)/2. , : O ((n + 1) ^ 2)/2)

0

N * (N + 1)/2 . , , O (N ^ 2).

0

N 2N t 4t

O (n ^ 2)

0

O (! n) ( ).

O (n ^ 2) , , , , , O (n ^ 2) .

-1

More articles:


All Articles