What is Rate Of Growth in Algorithms?

The rate at which the running time increases as a function of input is called rate of growth. Let us assume that you went a shop to buy a car and a cycle. If your friend sees you there and  asks what you’re buying then in general you say buying a car. This is because, cost of car is too big compared to cost of cycle (approximating cost of cycle to cost of car).

TotalCost = cost_of_car + cost_of cycle
TotalCost ≈ cost_of_car (approximation)

For the above mentioned 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 value of input size, n). As an example in the case below, 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 + 500 ≈ n4

Commonly used Rate of Growth:
Given below is the list of rate of growths which comes across in remaining chapters.

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 order
n log n	Linear Logarithmic	Sorting n items by ‘divide-and-conquer’ Merge Sort
n2	Quadratic	Shortest path between two nodes in a graph
n3	Cubic	Matrix Multiplication
2n	Exponential	Two Towers of Hanoi problem

Below diagram shows the relationship between different rates of growth.