Lesson 2

Often in discrete mathematics and computer science, we are interested not in the exact value of some function \(f(n)\), but in how quickly its value increases as \(n\) grows. The easiest way to explain this is with an example where \(f(n)\) is the runtime of an algorithm (i.e., the number of steps the algorithm performs on input data of size \(n\)), but the growth rate estimates we obtain are used far beyond just algorithms. They are also necessary and important in bioinformatics, combinatorics, cryptography, coding theory, game theory, and other areas.

Let \(f(n)=2n^{2}+3n+5\) be the runtime of some algorithm. As you may have already seen, such precise runtime is usually not specified. For example, here we can discard the terms \(3n\) and \(5\): at large \(n\), they anyway have much less impact on the result than the \(n^{2}\) term. After this, we are left with \(2n^{2}\), but we go even further and discard the multiplier \(2\) (we still do not know exactly how much time each individual step of our algorithm takes on a real computer). After all this, we are left with just \(n^{2}\), and it is often said that \(f(n)\) grows no faster than quadratically. We will write this as (we will formally introduce this notation soon): \[f(n) \preceq n^{2}.\] The fact that \(f(n)\) grows quadratically allows us to make such convenient conclusions: when \(n\) becomes two times larger, \(f(n)\) becomes roughly four times larger. Let's verify this experimentally.

def f(n):
    return 2 * n ** 2 + 3 * n + 5


n = 10 ** 5
print(f(2 * n) / f(n))

3.999969999700012