The Growth of Functions • In both computer science and in mathematics, there are many times when we care about how fast a function grows. • In computer science, we want to understand how quickly an algorithm can solve a problem as the size of the input grows. ○ We can compare the efficiency of two different algorithms for solving the same problem. ○ We can also determine whether it is practical to use a particular algorithm as the input grows. ○ We’ll study these questions in Section 3.3. • Two of the areas of mathematics where questions about the growth of functions are studied are: ○ number theory (covered in Chapter 4) ○ combinatorics (covered in Chapters 6 and 8) Big-O Notation • Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. • We say that f(x) is O(g(x)) if there are constants C and k such that ○ |f(x)|≤C|g(x)| whenever xk. • This is read as “f(x) is big-O of g(x)” or “g asymptotically dominates f.” • The constants C and k are called witnesses to the relationship f(x) is O(g(x)). • Only one pair of witnesses is needed. Some Important Points about Big-O Notation • If one pair of witnesses is found, then there are infinitely many pairs. • We can always make the k or the C larger and still maintain the inequality |f(x)|≤C|g(x)| . • If f(x) is O(g(x)) and g(x) is O(hx)) then f(x) is O(hx)) • You may see “ f(x)=O(g(x))” instead of “ f(x) is O(g(x)).” • But this is an abuse of the equals sign since the meaning is that there is an inequality relating the values of f and g, for sufficiently large values of x. • It is ok to write f(x)∈O(g(x)), because O(g(x)) represents the set of functions that are O(g(x)). • Usually, we will drop the absolute value sign since we will always deal with functions that take on positive values. Using the Definition of Big-O Notation • Example: Show that f(x)=x^2+2x+1 is O(x^2 ). ○ Since when x1, xx^2 and 1x^2 ○ 0≤x2+2x+1≤x2+2x2+x2−4x^2 ○ Can take C = 4 and k = 1 as witnesses to show that f(x) is O(x^2 ) ○ Alternatively, when x2, we have 2x≤x^2 and 1x^2. ○ Hence, 0≤x2+2x+1≤x2+x2+x2=3x^2 when x2. ○ Can take C = 3 and k = 2 as witnesses instead. • Example: Show that 7x^2 is O(x^3) ○ When x7, 7x2x3. ○ Take C =1 and k = 7 as witnesses to establish that 7x^2 is O(x^3). ○ (Would C = 7 and k = 1 work?) Yes • Example: Show that n^2 is not O(n) ○ Suppose there are constants C and k for which n^2≤Cn, whenever nk. ○ Then n≤ C must hold for all nk. A contradiction! Big-O Estimates for Polynomials • Let f(x)=a_n x^n+a_(n−1) x^(n−1)+…+a_1 x+a_0 where a_0,a_1,…a_n are real numbers with a_n≠0 • Then f(x) is O(x_n). • |f(x)| = |a_n x^n + a_(n−1) x^(n−1)+…+a_1 x+a_0 | • ≤ |an|xn + |an−1| xn−1 + ∙∙∙ + |a1|x1 + |a0| • = x_n (|a_n |+|a_(n−1) |/x +…+|a1|/x_(n−1) +|a_0 |/x_n ) • ≤ x_n (|a_n |+ |a_(n−1) |+…+ |a_1 |+ |a_0 |) • Take C=|a_n |+|a_(n−1) |+…+ |a_0 | and k=1. • Then f(x) is O(x^n). • The leading term a_n x^n of a polynomial dominates its growth. Big-O Estimates for Some Important Functions • Example: Use big-O notation to estimate the sum of the first n positive integers. ○ 1+2+…+n≤n+n+…+n=n^2 ○ 1+2+…+n is O(n^2 ) taking C=1 and k=1 • Example: Use big-O notation to estimate the factorial function f(n)=n!=1×2×…×n ○ n!=1×2×…×n≤n×n×…×n^n ○ n! is O(n^n ) taking C=1 and k=1 • Example: Use big-O notation to estimate logn! ○ Given that n!n^n ○ then logn!≤n⋅logn . ○ Hence, logn! is O(n logn ) taking C = 1 and k = 1. Display of Growth of Functions Combinations of Functions • If f_1 (x) is O(g_1 (x)) and f_2 (x) is O(g_2 (x)) then ○ (f_1+f_2)(x) is O(max{|g_1 (x)|,|g_2 (x)|} ). • If f_1 (x) and f_2 (x) are both O(g(x)) then ○ (f_1+f_2)(x) is O(g(x)). • If f_1 (x) is O(g_1 (x)) and f_2 (x) is O(g_2 (x)) then ○ (f_1 f_2)(x) is O(g_1 (x) g_2 (x)). Big-Omega Notation • Let f and g be functions from the set of integers/real numbers to the set of real numbers. • We say that f(x) is Ω(g(x)) if there are constants C and k such that |f(x)|≥C|g(x)| when xk • We say that “f(x) is big-Omega of g(x).” • Big-O gives an upper bound on the growth of a function, while Big-Omega gives a lower bound. • Big-Omega tells us that a function grows at least as fast as another. • f(x) is Ω(g(x)) if and only if g(x) is O(f(x)). • This follows from the definitions. • Example: Show f(x)=8x3+5x2+7 is Ω(g(x)) where g(x)=x^3 ○ f(x)=8x3+5x2+7≥8x^3 for all positive real numbers x ○ Is it also the case that g(x)=x^3 is O(8x3+5x2+7)? Yes Big-Theta Notation • Let f and g be functions from the set of integers/real numbers to the set of real numbers. • The function f(x) is Θ(g(x)) if f(x) is O(g(x)) and f(x) is Ω(g(x)) • We say that ○ “f is big-Theta of g(x)” ○ “f(x) is of order g(x)” ○ “f(x) and g(x) are of the same order.” • f(x) is Θ(g(x)) if and only if there exists constants C_1, C_2 and k such that C_1 g(x)f(x)C_2 g(x) if xk. • This follows from the definitions of big-O and big-Omega. • When f(x) is Θ(g(x)) it must also be the case that g(x) is Θ(f(x)) • Note that f(x) is Θ(g(x)) if and only if it is the case that f(x) is O(g(x)) and g(x) is O(f(x)). • Sometimes writers are careless and write as if big-O notation has the same meaning as big-Theta. Examples of Big-Theta Notation • Example 1: Show that the sum of the first n positive integers is Θ(n^2 ) ○ Let f(n) = 1 + 2 + ∙∙∙ + n. ○ We have already shown that f(n) is O(n^2). ○ To show that f(n) is Ω(n^2), we need a positive constant C such that f(n) Cn^2 for sufficiently large n. ○ Summing only the terms greater than n/2 we obtain the inequality 1 + 2 + ∙∙∙ + n ≥ ⌈n/2⌉+(⌈n/2⌉+1)+…+n ≥ ⌈n/2⌉+⌈n/2⌉+…+⌈n/2⌉ = (n−⌈n/2⌉+1)⌈n/2⌉ ≥ (n/2)(n/2) = n^2/4 ○ Taking C = 1/4, f(n) Cn^2 for all positive integers n. ○ Hence, f(n) is Ω(n^2), and we can conclude that f(n) is Θ(n^2). • Example 2: Show that f(x)=3x^2+8x logx is Θ(x^2) ○ f(x)=3x^2+8x logx≤11x^2 for x 1, ○ since 0 ≤8x logx≤ 8x^2. ○ Hence, 3x^2+8x logx is O(x^2). ○ x^2 is clearly O(3x^2+8x logx) ○ Hence, 3x^2+8x logx is Θ(x^2)
