0
$\begingroup$

Hi all i'm trying to predict/calculate the time complexity of an algorithm but i'm having some difficulties with the summations

the algorithm:

for(int i = 0; i < N; i++)
    for(int j = 0; j < i * i; j++)
        for(int k = 0; k < i; k++)
            //operation

So far I have to following: $$ \displaystyle\sum_{i=0}^{N-1} \sum_{j=0}^{i^2-1} \sum_{k=0}^{i-1} 1 $$ $$ = \displaystyle\sum_{i=0}^{N-1} \sum_{j=0}^{i^2-1} i $$

But now I'm stuck with the upper bound. I thought something like this $$ = \displaystyle\sum_{i=0}^{N-1} \frac{n^2(n^2+1)}{2} $$

But if i take a look at the algorithm it will be at most $O(n^4) $ ... Thanks in advance!

$\endgroup$
1
$\begingroup$

Following your derivation:

$$\sum_{i=0}^{N-1}\sum_{j=0}^{i^2-1}i =\sum_{i=0}^{N-1} i^3 =\sum_{i=0}^{N-1} O(N^3) =O(N^4)$$

Notice that $\sum_{j=0}^{i^2 -1}i$ equals $i^2 \cdot i$ since the index is $j$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.