Big-O De Nition

Introduction IAsymptoticsComputer Science & Engineering 235: Discrete MathematicsRecall that we are really only interested in the Order of Growth ofan algorithm’s complexity.How well does the algorithm perform as the input size grows;n Christopher M. Bourkecbourke@cse.unl.eduWe’ve seen how to mathematically evaluate the cost functions ofalgorithms with respect to their input size n and their elementaryoperation.However, it suffices to simply measure a cost function’s asymptoticbehavior.IntroductionIntroduction IMagnitude GraphIn practice, specific hardware, implementation, languages, etc. willgreatly affect how the algorithm behaves. However, we want tostudy and analyze algorithms in and of themselves, independent ofsuch factors.For example, an algorithm that executes its elementary operation10n times is better than one which executes it .005n2 times.Moreover, algorithms that have running times n2 and 2000n2 areconsidered to be asymptotically equivalent.Big-O DefinitionBig-Omega DefinitionDefinitionDefinitionLet f and g be two functions f, g : N R . We say thatf (n) O(g(n))(read: f is Big-“O” of g) if there exists a constant c R andn0 N such that for every integer n n0 ,f (n) cg(n)IBig-O is actually Omicron, but it suffices to write “O”IIntuition: f is (asymptotically) less than or equal to gIBig-O gives an asymptotic upper boundLet f and g be two functions f, g : N R . We say thatf (n) Ω(g(n))(read: f is Big-Omega of g) if there exist c R and n0 N suchthat for every integer n n0 ,f (n) cg(n)IIntuition: f is (asymptotically) greater than or equal to g.IBig-Omega gives an asymptotic lower bound.

Big-Theta DefinitionIllustrative ExampleIDefinitionILet f and g be two functions f, g : N R . We say thatf (n) Θ(g(n))IIIf (n) O(g(n)) if g(n) eventually dominates f (n)Let f (n) 100n2 , g(n) n3For n 100, f (n) g(n)At n 100, f (n) g(n)For n 100, g(n) f (n)(read: f is Big-Theta of g) if there exist constants c1 , c2 R andn0 N such that for every integer n n0 ,c1 g(n) f (n) c2 g(n)IIntuition: f is (asymptotically) equal to g.If is bounded above and below by g.IBig-Theta gives an asymptotic equivalence.Asymptotic Properties ITheoremFigure : g(n) dominates for all n 100Asymptotic Properties IISome obvious properties also follow from the definition.For f1 (n) O(g1 (n)) and f2 O(g2 (n)),f1 (n) f2 (n) O(max{g1 (n), g2 (n)})This property implies that we can ignore lower order terms. Inparticular, for any polynomial p(n) with degree k, p(n) O(nk ).1In addition, this gives us justification for ignoring constantcoefficients. That is, for any function f (n) and positive constant c,CorollaryFor positive functions, f (n) and g(n) the following hold:IIf (n) Θ(g(n)) f (n) O(g(n)) and f (n) Ω(g(n))f (n) O(g(n)) g(n) Ω(f (n))The proof is left as an exercise.cf (n) Θ(f (n))1More accurately, p(n) Θ(nk )Asymptotic Proof TechniquesAsymptotic Proof TechniquesDefinitional ProofDefinitional Proof - Example IProving an asymptotic relationship between two given functionsf (n) and g(n) can be done intuitively for most of the functionsyou will encounter; all polynomials for example. However, this doesnot suffice as a formal proof.To prove a relationship of the form f (n) (g(n)) where isone of O, Ω, or Θ, can be done simply using the definitions.ExampleLet f (n) 21n2 n and g(n) n3 . Our intuition should tell usthat f (n) O(g(n)). Simply using the definition confirms this:21n2 n cn3holds for, say c 3 and for all n n0 8 (in fact, an infinitenumber of pairs can satisfy this equation).

Asymptotic Proof TechniquesAsymptotic Proof TechniquesDefinitional Proof - Example IIDefinitional Proof - Example IIProof.ExampleLet f (n) n2 n and g(n) n3 . Find a tight bound of the formf (n) (g(n)).Our intuition tells us thatf (n) O(n3 )IIIf n 1 it is clear that n n3 and n2 n3 .Therefore, we have thatn2 n n3 n3 2n3IThus, for n0 1 and c 2, by the definition of Big-O, wehave that f (n) O(g(n)).Asymptotic Proof TechniquesAsymptotic Proof TechniquesDefinitional Proof - Example IIIDefinitional Proof - Example IIIProof.IExamplen34n2Let f (n) and g(n) form f (n) (g(n)).n2 .Find a tight bound of theHere, our intuition should tell us thatf (n) Ω(g(n))Limit MethodNow try this one:f (n) n50 12n3 log4 n 1243n12 245n6 log n 12 log3 n log nn 12g(n) 12n50 24 log14 n43 logn5Using the formal definitions can be very tedious especially whenone has very complex functions. It is much better to use the LimitMethod which uses concepts from calculus.IIIf n 0 thenAs before, if n 1,n3 n3 4n2n2 n3Thus, when n 1,n2 n3 n3 4n2IThus by the definition of Big-Ω, for n0 1, c 1, we havethat f (n) Ω(g(n)).Limit Method ProcessSay we have functions f (n) and g(n). We set up a limit quotientbetween f and g as follows: 0then f (n) O(g(n))f (n) c 0 then f (n) Θ(g(n))lim n g(n) then f (n) Ω(g(n))IJustifications for the above can be proven using calculus, butfor our purposes the limit method will be sufficient forshowing asymptotic inclusions.IAlways try to look for algebraic simplifications first.

l’Hôpital’s Rulel’Hôpital’s Rule IJustificationExample: prove that log n O(n); setting up a limit:limn log n ?nWhy do we have to use l’Hôpital’s Rule? Consider the followingfunction:If f and g both diverge or converge on zero, then you need toapply l’Hôpital’s Rule.Theoremf (x) sin xxWhat is f (0)?(l’Hôpital’s Rule) Let f and g, if the limit between the quotientf (n)g(n) exists, it is equal to the limit of the derivative of thedenominator and the numerator.limn Clearly, sin 0 0 so you may say that f (0) 0. However, thedenominator is also zero so you may say f (0) , but both arewrong.f (n)f 0 (n) limg(n) n g 0 (n)l’Hôpital’s Rule IIl’Hôpital’s Rule IIIJustificationJustificationObserve the graph of f (x):Clearly, though f (x) is undefined at x 0, the limit still exists.Applying l’Hôpital’s Rule gives us the correct answer:limx 0Figure : f (x) sin x0cos x 1x01sin xxLimit MethodLimit MethodExample 1Example 1 - Proof AProof.ExampleLet f (n) 2n , g(n) 3n . Determine a tight inclusion of the formf (n) (g(n)).What’s our intuition in this case?IWe prove using limits.IWe set up our limit,limn If (n)2n ng(n)3Using l’Hôpital’s Rule will get you no where:2n0(ln 2)2n 0n3(ln 3)3nBoth numerator and denominator still diverge. We’ll have touse an algebraic simplification.

Limit MethodLimit MethodExample 1 - Proof BExample 2Continued.IUsing algebra,2n n 3nlimII n23Now we use the following Theorem 0n1lim α n without proof:if α 1if α 1if α 1ExampleLet f (n) log2 n, g(n) log3 n2 . Determine a tight inclusion ofthe form f (n) (g(n)).What’s our intuition in this case?Therefore we conclude that the quotient converges to zerothus,2n O(3n )Limit MethodLimit MethodExample 2 - Proof AExample 2 - Proof BContinued.Proof.IWe prove using limits.IWe set up our limit,And we get thatlimlimn IIn f (n)log2 n g(n)log3 n2f (n)g(n) Here, we have to use the change of base formula forlogarithms:logβ nlogα n logβ αlog2 (n)log3 (n2 )log2 n2 log2 nlog2 3log2 32 .7924 . . . ILimit Properties So we conclude that f (n) Θ(g(n)).Useful Identities & DerivativesSome useful derivatives that you should memorize includeA useful property of limits is that the composition of functions ispreserved.ILemma(nk )0 knk 11ln (b)nI (f1 (n)f2 f10 (n)f2 (n)n0I (c ) ln (c)cn Careful!I(logb (n))0 (n))0For the composition of addition, subtraction, multiplication anddivision, if the limits exist (that is, they converge), thenlim f1 (n) lim f2 (n) lim f1 (n) f2 (n)n n n f1 (n)f20 (n) (product rule)Log IdentitiesIChange of Base Formula: logb (n) I log (nk )I k log (n)log (ab) log (a) log (b)logc (n)logc (b)

Efficiency ClassesLittle-o Definition og (n))O(n)O(logk (n))O(n2 )O(n3 )O(nk ) for any k 0O(2n )O(2f (n) ) for f (n) Ω(n)For example, n!Asymptotic notation provides loose bounds (except for Θ). Thesebounds are sufficient for algorithm analysis but for manyapplications it is much more accurate to use little-o andlittle-omega notation.Conveniently, the definition of o and ω are exactly what we getwhen we use the limit method.Table : Some Efficiency ClassesLittle-o Definition IILittle-o ExamplesDefinitionLet f and g be two functions, f, g : N R . We say thatf (n) o(g(n))(read: f is in little-o of g) iflimn Some examples that we provide without proof: In o(n)IIf (n) 0g(n)Alternatively, f (n) o(g(n)) means that for any real numberc 0, there exists n0 such that f (n) cg(n) for all n n0 .IIIIILittle-o can be interpreted as “f is strictly less than (never equalto) g.”Little-omega Definitionn o(n log log n)n log log n o(n log n)n log n o(n2 )nα o(nβ ) α, β R, α βαn o(β n ) α, β R, α βn o(n1 )f (n) 6 o(f (n))Little Asymptotics IPropertiesDefinitionLet f and g be two functions, f, g : N R . We say thatf (n) ω(g(n))Note that though simply using the limit method gives us thesebounds. That is,f (n) o(g(n)) f (n) O(g(n))(read: f is little-omega of g) iflimn f (n) g(n)Alternatively, f (n) ω(g(n)) means that for any real numberc 0, there exists n0 such that f (n) cg(n) for all n n0 .Little-omega can be interpreted as “f is strictly greater than(never equal to) g.”andf (n) ω(g(n)) f (n) Ω(g(n))However, the converses do not hold.

Little Asymptotics IISoft-O Notation IPropertiesHere are some examples of little-omega relationships.IIIIn! ω(2n )Logrithmic factors contribute very llittle as n .nα o(nα )If f (n) O(g(n) · logk n) thennα ω(nα )f (n) 6 ω(f (n))Note that f (n) o(g(n)) g(n) ω(f (n)) still holds.Also, f (n) 6 o(g(n)) and f (n) 6 ω(g(n)) f (n) Θ(g(n)).SummaryAsymptotics is easy, but remember:IAlways look for algebraic simplificationsIYou must always give a rigorous proofIUsing the limit method is always the bestIAlways show l’Hôpital’s Rule if need beIGive as simple (and tight) expressions as possibleSoft-O notation, Õ is used to ignore log factors:f (n) Õ(g(n))

Big-Theta De nition De nition Let f and g be two functions f;g :N ! R .We say that f(n) 2 ( g(n)) (read: f is Big-Theta of g) if there exist constants c1;c2 2 R and n0 2 N such that for every integer n n0, c1g(n) f(n) c2g(n) I Intuition: f is (asymptotically ) equal to g. I f is bounded above and below by g. I Big-