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.


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.

  • $\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
    Nov 7 '21 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$ Nov 7 '21 at 6:16

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.