This is an old revision of the document!
2.2 Asymptotic Order of Growth
Asymptotic Upper Bounds
- Let T(n) be a function(let's assume it is the worst-case running time of a certain algorithm on an input of size n.
- Given another function f(n),we say that T(n) is O( f(n)) (T(n) is order f(n))if for sufficiently large n, the function T(n) is bounded above by a constant multiple of f(n). We can write this relation as T(n) = O(f(n)). To be precise, T(n) is O(f(n)) if there exist constants c > 0 and n0 >= 0 such that for all n >= n0,we have T(n) < = c. The constant c works for all n,doesn't depend on n. In this case, we say that T is asymptotically upper-bounded by f.
