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:

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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