*2.4K*

The rate at which running time increases as a function of input is called Rate of Growth.

Let us assume that you went to a shop to buy a car and a cycle. If your friend sees you there and asks what you are buying then in general we say buying a car. This is because. cost of a car is too big compared to cost of cycle (approximating the cost of cycle to the cost of a car).

Total Cost = cost_of_car + cost_of_cycle

Total Cost ≈ cost_of_car (approximation)

For the above example, we can represent the cost of car and cost of cycle in terms of function and for a given function ignore the low order terms that are relatively insignificant (for large values of input size, n). As an example in the below case, n^{4} , 2n^{2}, 100n, and 500 are the individual costs of some function and approximate it to n^{4}. Since, n^{4} is the highest rate of growth.

n

^{4}+ 2n^{2}+ 100n + 500n ≈ n^{4}

## Commonly used Rate of Growth

Below is the list of rate of growths which we will see further.

Time Complexity |
Name |
Example |

1 | Constant | Adding an element to the front of a linked list |

log n | Logarithmic | Finding an element in a sorted array |

n | Linear | Finding an element in a unsorted array |

nlog n | Linear Logarithmic | Sorting n items by ‘Divide and Conquer’ |

n^{2} |
Quadratic | Shortest path between 2 nodes in a graph |

n^{3} |
Cubic | Matrix Multiplication |

2^{n} |
Exponential | The Towers of Hanoi problem |