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).
n4+ 2n2+ 100n + 500 ≈ n4
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.
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.