The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
181 views
for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
        for(k=1;k<=j;k++)
            for(l=1;l<=k;l++)
                printf("gate");
asked in Algorithms by (21 points) | 181 views

2 Answers

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

Answer is O(n^4)
answered by Boss (35k points)
0

I think its O(n2)

0 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$
answered by Veteran (367k points)

Related questions

+2 votes
3 answers
1
asked Oct 8, 2015 in Algorithms by admin Active (2.6k points) | 450 views
0 votes
2 answers
2
0 votes
1 answer
3
asked Jan 7, 2017 in Algorithms by firki lama Junior (887 points) | 115 views
+1 vote
1 answer
4
0 votes
2 answers
6
asked May 13, 2015 in Algorithms by kalpashri (283 points) | 168 views
0 votes
2 answers
7
asked May 11, 2016 in Algorithms by GateAspirant999 Active (2.7k points) | 472 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,071 questions
49,594 answers
162,952 comments
65,786 users