Find Big-Theta for the following program

929 Views Asked by At

The algorithm is:

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

If this was a big O problem I would say the loop is $O(n^4)$ because using the arithmetic sequence we can infer the nested for loop is $O\left(\frac{n^2(n^2+1)}{2}\right)$ but I'm not even sure about this. What's the difference when calculating Big Theta vs Big O?

1

There are 1 best solutions below

3
On

$f(n)\in\Theta(g(n))$ iff $f(n)\in O(g(n))$ and $g(n)\in O(f(n))$. In other words, the two functions grow at the "same rate."

Since $$\sum_{i=1}^{n}\sum_{j=1}^{i^{2}}1=n\left(n+1\right)\left(2n+1\right)/6\sim n^{3}/3,$$ it is indeed true that the runtime of the algorithm is in $O(n^3)$ (not $n^4$). But it is also true that the runtime of the algorithm is in $O(n^4)$, or $O(n!)$, etc..

However, can you say the same thing about $\Theta$?