The Growth of Functions and Big-O Notation

1 The Growth of Functions and Big-O NotationBig-O NotationBig-O Notation allows us to describe the aymptotic Growth of a function without concern for i)constant multiplicative factors, and ii) lower-order additive terms. For example, using Big-O Notation ,the functionf(n) = 3n2+6n+7 is assumed to have the same kind of (quadratic) Growth asg(n) = do we choose to ignore constant factors and lower-order additive terms? One kind of functionthat we often consider throughout this course isT(n), which represents the worst-case number ofsteps required by a an algorithm to process an input of sizen. FunctionT(n) will vary dependingon the computing paradigm that is used to represent the algorithm. For example, one paradigmmight represent the algorithm as a C program, while another might represent it as a sequence ofrandom-access machine instructions.

2 Now ifT1measures the number of algorithmic steps for the firstparadigm, andT2(n) measures the number of steps for the second, then, assuming that a paradigmdoes not include any unnecessary overhead, these two Functions will likely be within multiplicativeconstant factors of one another. In other words, there will exist two constantsC1andC2for whichC1T2(n) T1(n) C2T2(n).For this reason, Big-O Notation allows one to describe the steps of an algorithm in a mostly paradigm-indepenent manner, yet still be able to give meaningful representations ofT(n) by ignoring theparadignm-dependent constant (n) andg(n) be Functions from the set of nonnegative integers to the set of nonnegative realnumbers. ThenBig-Of(n) = O(g(n)) iff there exist constantsC >0 andk 1 such thatf(n) Cg(n) for everyn f(n) = (g(n)) iff there exist constantsC >0 andk 1 such thatf(n) Cg(n) for everyn f(n) = (g(n)) ifff(n) = O(g(n)) andf(n) = (g(n)).

3 Little-of(n) = o(g(n)) iff limn f(n)g(n)= f(n) = (g(n)) iff limn f(n)g(n)= .Note that a more succinct way of saying propertyP(n) is true for alln k, for some constantk is to say propertyP(n) holds forsufficiently largen . Although this phrase will be used oftenthroughout the course, nevertheless, when establishing a Big-O relationship between two Functions ,the student should make the effort to provide the value ofkfor which the inequality is functionsf(n) andg(n), to determine thebig-O relationshipbetweenfandg, we meanestablishing which, if any, of the above Growth relationships apply tofandg. Note that, if morethan one of the above relations is true, then we choose the one that gives the most information. Forexample, iff(n) = o(g(n)) andf(n) = O(g(n)), then we would simply writef(n) = o(g(n)), since itimplies the latter the Big-O relationship between i)f(n) = 6n2+ 2n+ 5 andg(n) = 50n2, andii) the samef(n) andg(n) = ResultsIn this section we provide some basic results that allow one to determine the Big-O Growth of afunction, or the Big-O relationship between two Functions , without having to revert to the (n) be a polynomial of degreeaandq(n) be a polynomial of degreeb.

4 Then p(n) = O(q(n)) if and only ifa b p(n) = (q(n)) if and only ifa b p(n) = (q(n)) if and only ifa=b p(n) = o(q(n)) if and only ifa < b p(n) = (q(n)) if and only ifa > bThus, Theorem 1 could have been invoked to prove thatf(n) = o(g(n)), wherefandgare thefunctions from Example (n),g(n),h(n), andk(n) be nonnegative integer Functions for sufficiently largen. Then f(n) +g(n) = (max(f(n),g(n))) iff(n) = (h(n)) andg(n) = (k(n)), thenf(n)g(n) = (h(n)k(n)) {O,o, , , }be one of the five Big-O relationships. Then iff(n) =R(g(n)), andg(n) =R(h(n)) thenf(n) =R(h(n)). In other words, all five of the big-Orelationships are the results of Theorems 1 and 2 to give a succinct expression for the Big-O growthoff(n)g(n), wheref(n) =nlog(n4+ 1) +n(logn)2andg(n) =n2+ 2n+ 3. Note: by succinct wemean that no constants or lower-order additive terms should appear in the limn f(n)g(n)=C, for some constantC >0, thenf(n) = (g(n)).

5 Proof of Theorem ,limn f(n)g(n)=Cmeans that, for every >0, there existsk 0, such that|f(n)g(n) C|< ,for alln k. In words,f(n)g(n)can be made arbitrarily close toCwith increasing values ofn. Removingthe absolute-value yieldsC <f(n)g(n)< C+ ,which implies(C )g(n)< f(n)<(C+ )g(n).SinceC >0 and >0 are constants, the latter inequalities implyf(n) = (g(n)) so long asC > , choosing =C/2, the result is >1 andb <0 are constants, with|b|< a. Prove thatan+bn= (an).4L Hospital s (n) andg(n) are both differentiable Functions with either1. limn f(n) = limn g(n) = , or2. limn f(n) = limn g(n) = f(n)g(n)= limn f (n)g (n).Example that for every >0, logn=o(n ).5 The following terminology is often used to describe the Big-O Growth of a (1)constant Growth (logn)logarithmic Growth (logkn), for somek 1polylogarithmic Growth (nk) for some positvek <1 sublinear Growth (n)linear Growth (nlogn)log-linear Growth (nlogkn), for somek 1polylog-linear growthO(nk) for somek 1polynomial Growth (nk), for everyk 1superpolynomial Growth (an) for somea >1exponential growthExample the above terminology to describe the Growth of the Functions from Examples 1and Use the definition of big- to prove thatnlogn= (n+nlogn2).

6 Provide Provide the Big-O relationship betweenf(n) =nlognandg(n) =n+ Prove thatf(n) = O(g(n)) if and only ifg(n) = (f(n)).4. Use the definition of big- to prove thatf(n) +g(n) = (max(f(n),g(n))).5. Prove that (n+a)b= (nb), for all realaandb >0. Explain why Theorem 1 and L Hospital srule be avoided when solving this problem?6. Prove that if limitn f(n)g(n)= 0, thenf(n) = O(g(n)), butg(n)6= O(f(n)).7. Prove or disprove: 2n+1= O(2n).8. Prove or disprove: 22n= O(2n).69. Use any techniques or results from lecture to determine a succinct big- expression for thegrowth of the function log50(n)n2+ log(n4) + 1000n2+ Prove or disprove: iff(n) = O(g(n)), then 2f(n)= O(2g(n)).11. Prove transitivity of Big-O : iff(n) = O(g(n)), theng(n) = O(h(n)), thenf(n) = O(h(n)).12. Ifg(n) =o(f(n)), then prove thatf(n) +g(n) = (f(n)).

7 13. Use L Hospital s rule to prove Theorem 1. Hint: assumeaandbare nonnegative integers andthata use L Hospital s rule to prove thatan= (nk), for every reala >1 and integerk Prove that logan= (logbn) for alla,b > Hints and Solutions1. Answers may vary. For this solution,n+nlogn2 nlogn+ 2nlogn= 3nlogn. Thus,nlogn (1/3)(n+nlogn2), for alln 1. SoC= 1/3 andk= From the previous exercise we havef(n) = (g(n)). Butf(n) = O(g(n)) withC=k= ,f(n) = (n).3. Set up the inequality for Big-O and divide both sides Two inequalities must be established, andC1= ,k1= 1,C2= 2,k2= 1 are adequateconstants (why?).5. Use Theorem Sincelimn f(n)g(n)= 0,we know thatf(n) g(n) for sufficiently largen. Thus,f(n) = O(g(n)).Now suppose it was true thatg(n) Cf(n) for some constantC >0, andnsufficiently dividing both sides byg(n) yieldsf(n)g(n) 1/Cfor sufficiently largen.

8 But sincelimn f(n)g(n)= 0,we know thatf(n)g(n)<1/C, for sufficiently largen, which is a contradiction. Therefore,g(n)6=O(f(n)).7. True, since 2n+1= 2 2,k= False. 22n= 4nandlimn 2n4n= limn 12n= use Exercise ( ).10. False. Considerf(n) = 2nandg(n) = Assumef(n) C1g(n), for alln k1andg(n) C1h(n), for alln k2. Therefore,f(n) C1g(n) C1C2h(n)for alln max(k1,k2).C=C1C2andk= max(k1,k2).12. Use Theorem 2 and the fact thatg(n)< f(n) fornsufficiently Letf(n) be a nonnegative-valued polynomial of degreea, andg(n) be a nonnegative-valuedpolynomial of degreeb, witha b. Since thekth derivative (as a function ofn) off(n) isequal to (na k) and that ofg(n) is equal to (nb k) it follows that L Hospital s rule appliesto the ratiof[k](n)/g[k](n) for allk < b. Moreover, upon applying the rule for thebth time, thenumerator will equal a polyhomial of degreea b, while the denominator will equal a (n) = (g(n)) ifa=bandf(n) = (g(n)) ifa > Since the derivative (as a function ofn) ofanequals (lna)an, it follows that thekth derivativeofandivided by thekth derivative ofnkequals lnkan/k!

9 , which tends to infinity. Therefore,an= (nk).15. By the Change of Base formula,logan=logbnlogba,and so logan=Clogbn, whereC= 1/logba. Therefore, logan= (logbn).9