Asymptotic analysis  

We say that

TA(n) = O ( g (n))

if there is a constant C > 0 such that

Limit
n->infinity
TA(n)
----------- = C
g(n)

 

Examples:

 
8n2 = O(8n2) = O(n2)

11n2 - 53n - 7 = O(n2)

57.2n = O( 2n)

3n != O( 2n)

 

A O(3n) algorithm is much slower than a O(2n) algorithm, which is much slower than a O(n2) algorithm.

[Prev][TOC]


CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000