Functions and Their Growth
Explore how functions represent algorithm performance and learn to compare their growth rates. This lesson helps you understand the basics of functions, how to analyze their outputs, and relate these concepts to algorithm complexity like insertion sort. Gain foundational skills to reason about algorithm growth intuitively.
We'll cover the following...
The yardstick to measure the performance of algorithms is specified in terms of functions. For the mathematically uninitiated, we explain functions below.
Functions
Think of a function like a machine or a blackbox that takes inputs from one end and spits outputs from the other end.
Let's consider the following function:
This is the traditional format of expressing a function, with n as the input fed to the "machine". The output of the "machine" is expressed in terms of the input; in the above function, the output is n2 defined in terms of the input n. The input n variable can take on different values and the output will vary accordingly. The below table captures the output values generated when n takes on different interger values.
| f ( n ) | n2 |
|---|