How do these 2 nested for loops differ in terms of Big Oh

41 Views Asked by At

Loop 1:

sum $\gets 0$
for $i\gets 1$ to $n$ do
$~~~~$ for $j \gets 1$ to $i^2$ do
$~~~~~~~~~$ sum $\gets$ sum + ary$[i]$

Loop 2:

sum $\gets 0$
for $i\gets 1$ to $n^2$ do
$~~~~$ for $j \gets 1$ to $i$ do
$~~~~~~~~~$ sum $\gets$ sum + ary$[i]$

I know this summation formula is $\sum_{i=1}^{n}i^2=n\left(n+1\right)\left(2n+1\right)/6\sim n^{3}/3,$

2

There are 2 best solutions below

0
On BEST ANSWER

The first one runs in $$ \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \Theta\left(n^3\right) $$ and the second one takes $$ \sum_{i=1}^{n^2} i = \frac{n^2\left(n^2+1\right)}{2} = \Theta\left(n^4\right) $$

0
On

The numbers of times the inner loop body is executed are

$$\sum_{i=1}^n\sum_{j=1}^{i^2}1=\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}6$$ and $$\sum_{i=1}^{n^2}\sum_{j=1}^i1=\sum_{i=1}^{n^2}i=\frac{n^2(n^2+1)}2.$$