736 views

2 Answers

1 votes
1 votes
Time complexity of nested loops is equal to the number of times the innermost statement is executed.

Answer is O(n^4)
1 votes
1 votes
$T(n) = \sum_{i=1}^{n} \sum_{j=1}^{i} \sum_{k=1}^{j} \sum_{l=1}^{k} c$

( Taking cost of printf as $c$)

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

$= c\sum_{i=1}^{n} \sum_{j=1}^{i} \frac{j.(j+1)}{2} $

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

$(d = c/2)$

$= d \sum_{i=1}^{n} \frac{i.(i+1)(2i+1)}{6} + \frac{i.(i+1)}{2})$

$= e \sum_{i=1}^{n} 2i^3 + 3i^2 + i + 3i^2 + 3i $

$(e = d/6)$

$= e \sum_{i=1}^{n} 2i^3 + 6i^2 +  4i $

Well, sum of the cubes of first $n$ natural numbers is $\left({\frac{n.(n+1)}{2}}\right)^2 = \Theta\left (n^4\right)$

So, our answer will also be $\Theta\left( n^4\right)$ due to the $i^3$ term going from $i=1..n$

Related questions

0 votes
0 votes
2 answers
1
kalpashri asked May 12, 2015
552 views
for(i=1;i<=n;i=i*2);for(j=1;j<=i;j=j+1);{}
0 votes
0 votes
2 answers
2
GateAspirant999 asked May 11, 2016
1,771 views
What is the time complexity of the following function: function(n) { for(i = 0; i < n; i = i*2) { for(j = 0; j < i; j++) { printf("*"); } } }
2 votes
2 votes
3 answers
3
admin asked Oct 8, 2015
1,206 views
int Test(int n) { if (n<=0) return 0; else { int i = random(n-1); return Test(i) + Test(n-1-i); } }Suppose the function $\text{random}()$ takes constant time, then what ...
0 votes
0 votes
1 answer
4
highheels10 asked Sep 15, 2018
470 views