retagged by
710 views
1 votes
1 votes

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; 
            }
}
retagged by

2 Answers

Best answer
2 votes
2 votes
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 ]$
selected by

Related questions

0 votes
0 votes
1 answer
1
sushmita asked Sep 28, 2018
848 views
Find the complexity of the following code fragment:int i = 1; for(; i <= n logn; i++) { for(i++; i <= n; i++) { printf("1") } }
0 votes
0 votes
2 answers
2
sushmita asked Sep 28, 2018
797 views
FIND THE TIME COMPLEXITYint i=1,j; for(;i <= n;i + +) { for(j = i; j <= nlogn; j∗= 2) { sum++; } }
1 votes
1 votes
1 answer
3
Shubhanshu asked May 9, 2017
629 views
How the worst case of merge sort is O(n^2) according to the given MIT assignment pdf:-explain ?
2 votes
2 votes
3 answers
4
sushmita asked Mar 21, 2017
7,031 views
For each group of functions, sort the functions in increasing order of asymptotic (big-O) complexity:$\begin{align*} &(a) \;\;f1(n) = n^{0.999999} * \log n \\ &(b) \;\;f2...