Welcome to Programming and Data Structures

We will not engage in the full mathematical formalism of Big-O notation. Our focus will be on understanding how to use Big O and to build an intuitive understanding of what different Big O categories mean.

That said, seeing the formal definition of Big-O notation can help illustrate the concept more clearly.

Put another way, to show that \(f(n) = O(g(n))\text{,}\) we need to pick a constant \(c\) to multiply the \(g(n)\) by and identify a threshold (\(n_0\)) beyond which the inequality \(f(n) \leq c \cdot g(n)\) holds.

For example, we want to show that \(f(n) = 3n + 6\) is \(O(n)\text{.}\) That means \(g(n) = n\) (the value inside the \(O( )\)). Thus we need to pick a \(c\) so that \(3n + 6 \leq c \cdot n\) (at least for large values of \(n\)). That is easy \(4n\) grows faster than \(3n\text{,}\) so we can choose \(c = 4\text{.}\) We then need to choose a threshold above which \(4n\) is greater than or equal to \(3n + 6\text{.}\) We can pick \(n_0 = 6\text{.}\) For all \(n \geq 6\text{,}\) the inequality \(3n + 6 \leq 4n\) holds true.

We could pick other constants that make the inequality true. We could use \(c = 100\) and \(n_0 = 1\) because \(3n + 6 \leq 100n\) for all \(n \geq 1\text{.}\) Or we could select \(c = 3\) and \(n_0 = 10\) because \(3n + 6 \leq 3n\) for all \(n \geq 10\text{.}\) We could even pick \(c = 100,000\) and \(n_0 = 1,000,000\) because \(3n + 6 \leq 100,000n\) for all \(n \geq 1,000,000\text{.}\) That last pair of values is pushing the bounds of what might be considered reasonable, but it still perfectly legal.

Another example. Suppose we want to show that \(f(n) = 2n^2 + 3n + 6\) is \(O(n^2)\text{.}\) That means \(g(n) = n^2\text{.}\) We need to pick a \(c\) and \(n_0\) so that \(2n^2 + 3n + 6 \leq c \cdot n^2\) at all values past \(n_0\text{.}\) We can choose \(c = 3\) because \(3n^2\) grows faster than \(2n^2 + 3n + 6\text{.}\) We then need to choose a threshold above which \(3n^2\) is greater than or equal to \(2n^2 + 3n + 6\text{.}\) We can pick \(n_0 = 100\text{.}\) For all \(n \geq 100\text{,}\) the inequality \(2n^2 + 3n + 6 \leq 3n^2\) holds true. We could pick a smaller \(n_0\text{,}\) but we do not have to, and the inequality is clearly true at \(n = 100\text{.}\)

Getting to pick the constants \(c\) and \(n_0\) is what makes Big-O so flexible. Picking \(c\) is what means that we do not have to worry about constant factors in the growth rate. Whatever constants there are in the dominant term, we can simply pick a larger constant for \(c\text{.}\) Picking \(n_0\) means we do not have to worry about the behavior of the function for small values of \(n\text{.}\) If the inequality does not hold for values of \(n\) less than \(x\text{,}\) we can just pick an \(n_0\) that is larger than that.

Note that these tools will not let us “prove” that a given function belongs in a slower growing category. If we wanted to show \(f(n) = 2n^2\) is \(O(n)\text{,}\) then we would have to find constants \(c\) and \(n_0\) so that \(2n^2 \leq c \cdot n\) for all \(n \geq n_0\text{.}\) No matter what values we pick, eventually \(2n^2\) will grow larger than \(c \cdot n\text{.}\) So we cannot find such constants and thus cannot show that \(2n^2\) is \(O(n)\text{.}\)