Ruminating on Constants in Big-O Notation
Explore the significance of constants in big-O notation to understand how functions compare in growth rates. This lesson clarifies why constants are essential for accurately assessing algorithm efficiency for sufficiently large inputs, helping you grasp the flexibility and usefulness of big-O in algorithm analysis.
We'll cover the following...
When trying to understand the definition of the big-O notation, it is natural to ask questions regarding the constants
Constants in big-O notation not unique
There are many legitimate values of for which is , in the example shown below. We can use the slider to see some valid and invalid values of (we show only integer values).
In fact, in general, given that is , there are infinitely many choices for the threshold value and the constant .
If something is true for all values of , then it must be true for all values of , all values of , and so on. Similarly, there are infinitely many choices of . If , then clearly ...