Click here to hide categories Click here to show left categories

User: Home          welcome : Guest          Log In / Register here     




Basic Concepts - Rate of growth

It is not possible to perform simple analysis on the algorithm to determine exact amount of time required by it. The first complication is that the exact amount of time will depend on the implementation of the algorithm and on the actual machine. Another complication is that the time requirements will depend on the amount of input data. So the estimate for the time required by an algorithm is represented as a function of the size of the input data.

Suppose M is an algorithm and suppose n is the size of input data. The complexity function f(n) of M increases as n increases. The rate of increase of f(n) is found by comparing f(n) with some standard functions, such as:

log2 n, n, n log2 n, n2, n3, 2n

Table for rate of growth of standard functions

According to the above table, the rates of growth are: The logarithmic function log2 n grows most slowly, the exponential function 2n grows most rapidly and the polynomial function nc grows according to the exponent c.

Share this article   |    Print    |    Article read by 1469 times
Author:
Ritika Sood
Lecturer in computer science....Love to do programming...Other interests are sports, freaking out with frnds, travel at beautiful places, watch movies, listen songs....
Related Articles: No related article
Related Interview Questions: No related interview question