Pitfalls of using asymptotic notation over a limited domain
Case study:
We prove that \(T(n) = O(n)\) when n is an exact power of 2.
If n is defined the following way however: $$ T(n) = \left\{ \begin{array}{l} n &if n = 1, 2, 4, 8... \ (powers \ of \ 2) \\ n^2 &otherwise \\ \end{array} \right. $$
We realize that \(T(n) = O(n^2)\) instead.
This is a result of only looking at the domain:
$$ \{n^{2p} \ | \ ∀ n, p ∈ Ζ \} $$