# 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 ∈ Ζ \} $$