Big O Notation

[aeck]

Question:

for ( j = 0; j < n; j++ )
{
for ( k = j; k < n; k++ )
{

<some operation>

}
}


Algebraic Expression: n(n+1) = n^2 + n

Big O Notation: O(n^2)

[helios]

The expression is correct save for a factor of 1/2. E.g. 3*3 + 3 = 12, but 1+2+3 = 6.
The big O is correct.

[aeck]

Thanks!

So the correct algebraic expression would be:

n(n+1)/2

?

[helios]

Yes. See https://en.wikipedia.org/wiki/Triangular_number