Posts

Showing posts with the label rate of growth

What is Rate Of Growth in Algorithms?

Image
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, n 4 , 2n 2 ,100n and 500 are the individual costs of some function and approximate it to n 4 . Since, n 4  is the highest rate of growth.                               n 4 + 2n 2 + 100n + 500 ≈ n 4 Commonly used Rate of Growth: Given below is the list of rate of growths