2.2 Asymptotic Order of Growth

• 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 n₀ >= 0 such that for all n >= n₀, 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. To find the upper bound f, we inflate the terms in the equation of T(n).

For instance, if T(n) = pn² + qn + r where p, q, r are positive constants,
For all n ≥ 1,
T(n) = pn² + qn + r ⇒ T(n) ≤ pn² + qn²+ rn²
pn² + qn²+ rn² = (p+q+r) n² = c n²
⇒ T(n) ≤ cn², where c = p+q+r
Thus, T(n) = O(n²)

• 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).
• To show that an upper bound found the best one possible, we need to express the notion that for arbitrarily large input sizes n,the function T(n) is at least a constant multiple of some specific function f(n). Thus we write T(n) = Ω(f(n))(T(n) is Ω(f(n))) if there exist constants if there exist constants ε > 0 and n₀ ≥ 0 such that for all n ≥ n₀ , we have T(n) ≥ ε · f(n)). In this case, T is asymptotically lower-bounded by f. the constant ε is fixed,and is independent of n. This time, we deflate the terms of the polynomial T instead of inflating them to find the lower bound.

For instance, if T(n) = pn² + qn + r where p, q, r are positive constants

For all n ≥ 0, T(n) = pn² + qn + r ≥ pn²
⇒ T(n) ≥ εn², where ε = p > 0

⇒T(n) = Ω(n)

• If we can show that a running time T(n) is both O(f(n)) and also Ω (f(n)),then we have found the right bound: T(n) grows exactly like f(n)to within a constant factor.
• If a function is both O(f(n)) and also Ω (f(n)), we say that T(n) is Θ(f(n)). In this case, we say that f(n) is an asymptotically tight bound for T(n).
• If we let f and g be two functions such that lim (n tends to infinity) of f(n) / g(n) exists and is equal to some number c > 0, then f(n) = Θ(g(n)).

• Transitivity:
  • If f = O(g) and g = O(h) then f = O(h)
  • If f = Ω(g) and g = Ω(h) then f = Ω(h)
  • If f = Θ(g) and g = Θ(h) then f = Θ(h)
• Sums of functions:
  • If f = O(h) and g = O(h) then f + g = O(h)
  • If f = Ω(h) and g = Ω(h) then f + g = Ω(h)
  • If f = Θ(h) and g = Θ(h) then f + g = Θ(h)
  • Let k be a fixed constant and let f₁,f₂,…,f_k and h be functions such that f_i = O(h) for all i. Then f₁ + f₂+…+ f_k = O(h).
    

• Polynomials: For a polynomial T(n) = a₀ + a₁n + … + a_dn^d of degree d, in which the coefficient a_d is positive, f = O(n^d)
• Logarithms: log_b n is the number x such that b ^x = n. If we round log_bn to the nearest integer, it is one less than the number of digits in the base-b representation of the number n.
  • For every b > 1 and every x > 0, log_bn = O(n<sup>x<sup>. * Exponentials : Let f(n) = rⁿ. For every r > 1 and every d > 0, n ^d = O(rⁿ).

These three functions are the most frequent functions encountered when analyzing running times. Logarithms grow more slowly than polynomials and polynomials grow more slowly than exponentials.