test = 0;
for( i = 0; i < n; ++i )
for(j = 0; j < i; ++j )
test++;
My trouble is calculating the cost for the inner loop. Since it will run whenever it is less than i, i'm guessing worst runtime of that inner loop would be O(i) which is essentially O(n) so then overall would be O(n^2)?
O(n^2) for the entire code.
More specifically, the test++ will be executed about (n-1)*n/2 times. But that still is called "O(n^2)" or "quadratic".
Big-O ignores any constant multiplier -- 1/2 in this case.
Also, it ignores any lesser components. Note (n-1)n/2 = (nn - n)/2. So the n*n is used and the n is ignored.
That particular bit of code is not very practical -- the for looping will take longer than ++. Furthermore, a good optimizer might run find some way to optimize it.
You said "the worst runtime". That is not really valid. It could be that the "worst" only occurs very infrequently. That is, you might end up with only O(n log n) in some other situation.
Another way to think through the issue: O(n^2) means that doubling n will approximately quadruple the execution time.
This is like O(n^2).
Your total processes is equal to n*(n-1)/2 instead of n*n which is same as O(n^2)
