Asymtotic Analysis

Running time:

–the number of primitive operations (steps) executed before termination

Typical Running Time Functions

•1 (constant running time):

–Instructions are executed once or a few times

•logN (logarithmic)

–A big problem is solved by cutting the original problem in smaller sizes, by a constant fraction at each step

•N (linear)

–A small amount of processing is done on each input element

•N logN

–A problem is solved by dividing it into smaller problems, solving them independently and combining the solution

•N2 (quadratic)

–Typical for algorithms that process all pairs of data items (double nested loops)

•N3 (cubic)

–Processing of triples of data (triple nested loops)

•NK (polynomial)

•2N (exponential)

–Few exponential algorithms are appropriate for practical use

If the base of a logarithm is changed from one constant to another, the value is altered by a constant factor.

Ex: log10 n * log210 = log2 n.

Base of logarithm is not an issue in asymptotic notation.

Exponentials with different bases differ by a exponential factor (not a constant factor).

Ex: 2n = (2/3)n*3n.