Menu
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.
416
The triangular number sequence is the representation of the numbers in the form of equilateral triangle arranged in a series or sequence. These numbers are in a sequence of 1, 3, 6, 10, 15, 21, 28, 36, 45, and so on. The numbers in the triangular pattern are represented by dots.
The nth triangular number in the sequence is the number of dots it would take to make an equilateral triangle with n dots on each side. The formula for the nth triangular number is (n)(n + 1) / 2.
0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666... (This sequence is included in the On-Line Encyclopedia of Integer Sequences (sequence A000217 in the OEIS).)
Checking using the method above shows that the 12th triangular number is 78.
Yes, N*(N+1)/2, when you drop the constants and lower-order terms, leaves you with N-squared.
142
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.
36
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
