Big Oh rules - How to argue in case of negative base Let us say you have a function $C_n = (-2)^n + 2^n$.
It would seem that it would be correct to assume that the running time of this algorithm would be $O(2^n)$.
However, how would I go about arguing this? The rule I had in mind would be that $a^n$ is $O(b^n)$ if $0 &lt; a \leq b$. But since $a$ is $&lt; 0$, this rule cannot be applied. How would one argue the relevancy of the roots in cases like this, where the specific conditions do not hold up?
If $C_n = -2^n + 2^n$, then this just simplifies to $C_n = 0$, so I assume that you mean $C_n = (-2)^n + 2^n$. Then:
$$
C_n \le |-2|^n + 2^n = 2^{n+1} = O(2^n).
$$