0
$\begingroup$

For any $n$ and any $x$, if one implements a loop to calculate:

$$\sum_{i=0}^n x^i$$

What is time complexity of said loop if we assume $x^i$ to have time complexity of $O(i)$?

What confuses me is the fact that in each iteration, $i$ will have a different value.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

With your assumption that computing $x^i$ has $O(i)$ complexity, the iteration with some $i$ will have complexity of $O(i)$ too (it simply adds $x^i$ to the current sum). So, complexity of each iteration can be taken $ci$ for some $c$. Total complexity of all iterations:

$ \sum_{i=1}^{n} ci = cn(n+1)/2 $

which belongs to $O(n^2)$.

But for an efficient method, you can refer to the formula for sum of a geometric progression.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So, because the $i$ in $O(i)$ of each iteration can vary, we take it as its worse, which is $i=n$, to then arrive at $O(ni)=O(n²)$? $\endgroup$
    – YzSun
    Commented Nov 7, 2021 at 0:15
  • $\begingroup$ If we take the internal steps' complexity as a loose bound (far from precise), we may get the final total complexity as loose too. So, generally it is a better idea to not replace $i$ by $n$ (though, in this case, you would arrive at the same answer $O(n^2)$). $\endgroup$
    – Nitin Verma
    Commented Nov 7, 2021 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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