Question

Solve the following time complexities

a) T (n)= n∑ n∑ 1

i=1 j=1

b) T(n) = n-1 ∑ n∑ c

i= 0 j= i+1

c) T(n) = n ∑ 1

i= 1

Answer 1

a) $T(n)=n\Sigma n\Sigma 1$

We know that,

$\Sigma 1= n$

So, $\Sigma n\times n=\Sigma n^2$

Here first term of series n, will be functioning as the constant,

So, $\Sigma n^2 = \frac{n(n+1)(2n+1)}{6}$

$\Rightarrow T(n)=n( \frac{2n^3+n^2+2n^2+n}{6})$

$\Rightarrow T(n)=\frac{2n^4+3n^3+n^2}{6}$

$\Rightarrow T(n)=\frac{n^4}{3}+\frac{n^3}{2}+\frac{n^2}{6}$

Hence the complexity of the given terms will be

$=O(n^4)+O(n^3)+O(n^2)$

Hence the complexity of the terms will be $O(n^4)$

b) $T(n)= (n-1)\Sigma n \Sigma c$

Here c is constant,

$\Sigma c = c\Sigma1 = cn$

$\Sigma n(cn)=c\Sigma n^2 =c\frac{n(n+1)(2n+1)}{6}$

$=\frac{c (n-1)(n^2+n)(2n+1)}{6}$

$=\frac{c(n-1)(2n^3+n^2+2n^2+n)}{6}$

$=\frac{c(2n^4+3n^3+n^2-2n^3-3n^2-n)}{6}$

$=\frac{c(2n^4+n^3-2n^2-n)}{6}$

Hence, the respective time complexity of the given function,

$=O(n^4)+O(n^3)-O(n^2)+O(n)$

Hence the complexity of the given function will be $O(n^4)$

c)

$T(n)=n\Sigma 1$

$=n\times n$

$=n^2$

Hence, the time complexity of the given function will be $O(n^2)$