Big O Notation

Aug 26, 2015 at 5:05pm
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)

Last edited on Sep 25, 2015 at 2:48am
Aug 26, 2015 at 5:08pm
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.
Aug 26, 2015 at 5:12pm
Thanks!

So the correct algebraic expression would be:

n(n+1)/2

?
Aug 26, 2015 at 5:16pm
Topic archived. No new replies allowed.