Functions and Their Growth

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:

$$f ( n ) = n^2$$

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 n² 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 ...