Question

Solve the following time complexity

T(n) = ∑ ∑ 1

𝑖

𝑗=0

𝑛−1

𝑖=1

Answer 1

Given,

$T(n)=\Sigma_{i=1}^{i=n} \Sigma_{j=1}^{n-1} (1)$

We know that,

$\Sigma_{j=1}^{n-1} (1)=(n-1)$

So complexity of this step will be $O(n)$

Now again,

$\Sigma_{i=1}^{i=n}(n-1)$

$=\Sigma_{i=1}^{i=n}(n)-\Sigma_{i=1}^{i=n}(1)$

$=\frac{n(n-1)}{2}-n$

$=\frac{n^2}{2}-\frac{n}{2}-n$

$=\frac{n^2}{2}-\frac{3n}{2}$

So the complexity of the steps will be as per the below-

$=\frac{1}{2}O(n^2)-\frac{3}{2}O(n)$

Hence the required final complexity will be $=O(n^2)$