Write short note on growth of functions.

1. We need to approximate the number of steps required to execute any algorithm because of the difficulty involved in expression or difficulty in evaluating an expression. We compare one function with another function to know their rate of growths.

2. If f and g are two functions we can give the statements like ‘f has same growth rate as g’ or ‘f has higher growth rate than g’.

3. Growth rate of function can be defined through notation.

   • θ-Notation (Same order) : This notation bounds a function to within constant factors. We say f(n) = θg(n) if there exist positive constants $n_0$, $c_1$ and $c_2$ such that to the right of $n_0$ the value of f(n) always lies between $c_1$g(n) and $c_2g(n)$ inclusive.

• O-Notation (Upper bound) : This notation gives an upper bound for a function to within a constant factor. We write f(n) = O(g(n)) if there are positive constants $n_0$ and c such that to the right of $n_0$, the value of f(n) always lies on or below cg(n).

• σ-Notation (Lower bound) : This notation gives a lower bound for a function to within a constant factor. We write f(n) = σg(n)) if there are positive constants $n_0$ and c such that to the right of $n_0$ , the value of f(n) always lies on or above cg(n).