I need to figure out how to calculate Big Oh (that is, O(N), etc.) values for statements inside double nested loops. Anyone know how? This relates to figurate numbers (http://en.wikipedia.org/wiki/Figurate_numbers)

this pertains to calculating worst-case efficiency through finding formulas for the number of total executions of each line of code of a sorting algorithm.

ex.--

-----------------

for (i = o; i < n; i++)

{

for (j = i; j < n; j++)

{

for(k=0; k<= 1; k++)

{

//statement

}

}

}

-----------------

--I know that the Big Oh value for the outermost loop is 2N+3 through manual

calculation.

--I know that the second or middle loop Big Oh value is (n^2+n)/2 via the figurate

formula (see wikipedia link above)

--I know what the third or inner-most loop Big Oh value is-- [(n(n+1)(n+2)/3!)+1]

and that I need to multiply this equation by one representing the number of

executions of the statement within the third or innermost loop, but what is the

formula for this statement?

Can anyone help point me in the right direction?