1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$.)

$\endgroup$
  • $\begingroup$ Thank you for your response! Could you elaborate on the, "1 comes from the control structure." What kind of control structures would result in something other then 1? If the algorithm was lets say, 1 to floor(sqrt(n)), and the ith iteration of the loop executes n-i steps, where do I start here? $\endgroup$ – Rngeezus Jan 10 '17 at 15:38
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 10 '17 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.