437 views
2 votes
2 votes

What is the correct time complexity in $\theta()$ ?

1 Answer

Best answer
2 votes
2 votes

Answer: $\Theta(n^3)$

The Loop Equation can be written as:-

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

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

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

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

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

$=(1/2)\{[(n(n+1)(2n+1)/6] + [(n(n+1)/2)]\}$

$=\Theta(n^3)$

selected by

Related questions

0 votes
0 votes
2 answers
1
radha gogia asked Jul 7, 2018
1,547 views
foo(int n) { for(int i=0 ; i<n ;i++) for(int j=i ; j<=i*i ;j++) if(j%i==0) { for(int k=0;k<j;k++) printf("hii"); } } How to proceed here for analyzing the time complexity...
3 votes
3 votes
1 answer
3
Sanjay Sharma asked Feb 20, 2018
1,040 views
An array A is of length n has log( n) distinct numbers.What is the time complexity of sorting A by best comparison based algorithm ?