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, n4 , 2n2, 100n, and 500 are the individual costs of some function and approximate it to n4. Since, n4 is the highest rate of growth.
n4 + 2n2 + 100n + 500n ≈ n4
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’ |
| n2 | Quadratic | Shortest path between 2 nodes in a graph |
| n3 | Cubic | Matrix Multiplication |
| 2n | Exponential | The Towers of Hanoi problem |
Video Explanation:
