Compute the worst case time complexity of the following algorithm, for i = 1 to n do for j = 1 to n do for k = 1 to i + j do print (i, j, k).

Question

 for i = 1 to n do 

    for j = 1 to n do 

        for k = 1 to i + j do 

            print (i, j, k).

So here is what I've got

$\sum_{i=1}^n \ \sum_{j=1}^n \ \sum_{k=1}^{i+j} C\ $

$C\sum_{i=1}^n \ \sum_{j=1}^n \ \sum_{k=1}^{i+j} 1\ $

$C\sum_{i=1}^n \ \sum_{j=1}^n \ (i+j) $

$C\sum_{i=1}^n \ i\sum_{j=1}^n \ j $

$C\sum_{i=1}^n \ i\frac{n (n+1)}{2} \ \ $

$ \frac{n (n+1)}{2} \ C\sum_{i=1}^n \ i\frac{n (n+1)}{2} \ \ $

$ \frac{n (n+1)}{2} \ C \frac{n (n+1)}{2} \ \ $

$ \frac{n (n+1)}{2} \ C\sum_{i=1}^n \ i\frac{n (n+1)}{2} \ \ $

$ C \ (n^{2} +n) \\$

And since the term with the highest exponent dominates

$O( n^2)$

Now I'm a complete beginner, and I came up with this solution by going over my notes.

For all I know this is completely wrong from step 1.

Was this the correct solution? If not how would I solve this problem?

Answer 1

You setup correctly but made a mistake. The complexity is $$ \begin{split} N &= C \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^{i+j} 1 \\ &= C \sum_{i=1}^n \sum_{j=1}^n (i+j) \\ &= C \sum_{i=1}^n \left[in + \frac{n(n+1)}{2}\right] \\ &= C \left[ n \frac{n(n+1)}{2} + n \frac{n(n+1)}{2}\right] \\ &= \frac{2Cn^2(n+1)}{2} \\ &= Cn^2(n+1) \\ &= \Theta\left(n^3\right). \end{split} $$