# Time complexity when loop index is an exponent

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)$$.
• 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²)$? Nov 7 '21 at 0:15
• 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)$). Nov 7 '21 at 6:16