Finding the Big O of a nested loop Structure

Question

I have a loop that looks something like the one shown below. I'm interested in finding Big O for this loop structure.

for i = 1 to n { // assume that n is input size
                         ...
                         for j = 1 to 2 * i {
                             ...
                             k = j;
                                 while (k >= 0) {
                                     ...
                                     k = k - 1;
                                 }
                         }
               }

From what I can gather is:

Outer-most loop runs 'n' times
The second loop runs '2n' times (assuming increment size is 1)
Inner-most loop runs '2n' times

So should the Big O of n be O(n^3) or will it be something different?

A concrete link to such problems and their solutions will be appreciated.

Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Paul Hankin, Oct 16 '16 at 14:18
The dupe link provides the tools for computing the big-O. You have a serious misconceptions though -- the j loop runs 2i times per iteration and the k loop runs j+1 times. You might get the same eventual answer by replacing i and j by n (and in this case you do), but you should have mathematical justification for why that's valid. You can often use wolfram alpha to do the necessary sums: https://www.wolframalpha.com/input/?i=sum(sum(j%2B1,+for+j%3D1+to+2i),+for+i%3D1+to+n) — Paul Hankin, Oct 16 '16 at 14:26
Thanks, this puts things into perspective. I've arrived at a conclusion from your comment. I'll post the answer below. — Khan, Oct 16 '16 at 16:53

Khan · Accepted Answer · 2016-10-16T17:28:07.143

Let I(), M(), T() be the running times for the inner loop, middle loop, and the entire program (outer-most loop). If we work from the inside out, we get:

Inner-most loop;
I(j) = Summation (1) //from k=0 to j
I(j) = j+1  //Using basic Summation expansion formula.

Middle loop
M(i) = Summation (I(j)) //from j=1 to 2i
M(i) = Summation (j+1)  //from j=1 to j=2i with I(j)'s values
M(i) = Summation (j) + Summation (1)  //both from j=1 to j=2i

Using the expansion formula for Summation (j) from j=1 to n is '(n(n+1)/2)' and the fact that Summation (1) from j=1 to n is 'n', we get:

M(i) = 2i^2 + 3i

Outer-most loop:

T(n) = Summation (2i^2 + 3i)  //Summation from i=1 to n
T(n) = Summation (2i^2) + Summation (3i)  //both summations from i=1 to n
T(n) = 2*Summation (2i^2) + 3*Summation (i)  //both summations from i=1 to n
T(n) = (2(2n^3 + 3n^2 + n))/6) + (3(n(n+1))/2)  //using summation expansion formulas
T(n) = (4n^3 + 15n^2 + 11n)/2

Which means Big O of n be T(n^3).

Note: Basic summation expansion formulas for summation expansion can be found on the first page of this link

Thanks for the hint @Paul Hankin

Finding the Big O of a nested loop Structure

1 Answers1