# Determining Asymptotic Tight Bound

Let's say I have an algorithm, MyAlgo(n) as follows:
for i: = 1 to n do
(something)
Where in the i-th iteration, (something) executes i^2 steps.
How can I determine an asymptotic tight bound (Big-Theta) on the running time of this algorithm? I know I have to determine Big O and Big Omega, but since the actual algorithm isn't shown, I don't know where to start.

If the number of steps executed in the $i$th iteration is $i^2$, then the number of steps overall will be asymptotic to $$\sum_{i=1}^n (C+i^2) = \Theta(n^3),$$ for some constant $C$ that comes from the loop control (i.e., incrementing $i$ and checking whether it equals $n$).
To see that $\sum_{i=1}^n (C+i^2) = \Theta(n^3)$, use $$\sum_{i=1}^n (C+i^2) \leq n(C+n^2) = Cn+n^3 = O(n^3), \\ \sum_{i=1}^n (C+i^2) \geq \sum_{i=n/2}^n i^2 \geq (n/2) (n/2)^2 = n^3/8 = \Omega(n^3).$$ (In fact, $\sum_{i=1}^n i^2 \approx n^3/3$, as can be seen by approximating it by the integral $\int_1^n i^2 \, di$, or by using the exact formula $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$.)
• The number 1 here is completely arbitrary. Any constant would do. I changed my answer accordingly. Whatever machine model you are using, it probably takes more than 0 steps to effect the control structure of the loop, e.g. advancing the index $i$ and checking whether it equals $n$ or not. – Yuval Filmus Jan 10 '17 at 17:04