Home Theory What is Rate of Growth of Algorithm?

What is Rate of Growth of Algorithm?

by nikoo28
0 comment

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:

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More