[Math] Time complexity of the following code snippet

algorithmsanalysis-of-algorithmsasymptoticscomputational complexitysequences-and-series

Question

Time complexity of the following code snippet -:

sum = 0;
for (int i = 0; i < n; i++)
  for (int j = 0; j < i*i; j++)
    for (int k = 0; k < j; k++)
      sum++;

My approach

$\text{sum}$ is running exactly $j$ times for each each $k$

As an example , if i take

$i=1 \Rightarrow \text{j will run 1 time} \Rightarrow \text{sum will run}\,\, 1\,\, \text{time} $

$i=2 \Rightarrow \text{j will run 4 time}$ i.e for $j=0,1,2,3$

Sum will be execute total of $0+1+2+3$

$i=n \Rightarrow \text{j will run } n^{2}$ time i.e for $j=0,1,2,3,…n^2$
sum will be executed

$1+2+3+..n^2 \approx n^4$

then it should be $O(n^4)$

Am i right?
Please help

Best Answer

\begin{align} \sum_{i=1}^n \sum_{j=1}^{i^2} \sum_{k=1}^j 1&=\sum_{i=1}^n \sum_{j=1}^{i^2} j\\ &=\sum_{i=1}^n\frac{i^2}{2}(i^2+1)\\ &=\sum_{i=1}^n\frac{i^4+i^2}{2}\\ &= \Theta(n^5) \end{align}

Related Question