MIT ASSIGNMENT

Question

Find the complexity of the following function when called with some integer n:

void foo(n)
{
    int i,j,k,x=0;
    for (i=1 ; i <= n ; i++)
        for (j=1 ; j <= i * i ; j++) 
            for ( k = 1 ; k <= j ; k++)
            {
                x=x+10; 
            }
}

Comments

 sushmita 

Please share the link of the assignment.

Answer 1

Short Answer let T(n) be time complexity of function then O($n^{5}) \leq T(n) \leq \Omega (n)$

Brief answer:

For each iteration of outer most loop (i$^{th}$ loop) the inner loop (j$^{th}$ loop and k$^{th}$ loop) will execute i$^{2}$ times

we can summarize it as $\sum_{i=1}^{n} \frac{i^{2}*(i^{2}+1)}{2}$

$\sum_{i=1}^{n} \frac{i^{4}+i^{2}}{2}$

$\sum_{i=1}^{n} \frac{i^{2}}{2}+\sum_{i=1}^{n} \frac{i^{4}}{2}$

Final equation will be

$\left [ \frac{6n^{5}+15n^{4}+20n^{3}+15n^{2}+4n}{60} \right ]$

Comments

okay understood the formula. i was not getting n^5 initially in my expression. thanks

---

I think T(n) will be O(n^5), because

first loop runs n times

second loop runs (n-1)^2 times as third loop also same

multiplying higher powers we get n^5

---

it should be $O(n^{5})$ only.

Everything is correct but the last part should give $\theta(n^{5})$

$\sum _{i=1}^{n} i^{4}=\Theta (n^5)$

Answer 2

better explanation here

https://gateoverflow.in/256211/advance-test-algorithms