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.
|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|
|2n||Exponential||The Towers of Hanoi problem|