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