We say that
if there is a constant C > 0 such that
Limit n->infinity |
T_{A}(n) ----------- = C g(n) |
Examples:
11n^{2} - 53n - 7 =
57.2^{n} =
3^{n }!=
8n^{2} = O(8n^{2})
= O(n^{2})O(n^{2})O( 2^{n})O( 2^{n})
A O(3^{n})
algorithm is much slower than a O(2^{n}) algorithm,
which is much slower than a O(n^{2}) algorithm.
CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000