I think its O(n^{2})

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

+1 vote

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

Answer is O(n^4)

Answer is O(n^4)

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$

( 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$

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 487
- Exam Queries 436
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,194 questions

43,647 answers

124,088 comments

42,929 users