What is time complexity?

Question

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

Comments

@h4kr Continuing @Kabir5454 ‘s equation:-

$\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)$

---

Correct

---

solving  by matrix entry

1…………………….

1    2……………………

1    2    3………………..

……….

1    2   3………………….………………n-2

sum of the all entry of  n-2 *n-2 matrix =(n-2)*(n-1)(n-2)/2  

here half of the entry fill  hence devide by 2   

means it is asymptotically eqaul to theta(n^3)

Answer 1

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