Transcription of Big O and Little o Notation - CMU Statistics
1 14:51 Friday 18thJanuary, 2013 Appendix BBigOand LittleoNotationIt is often useful to talk about therateat which some function changes as its argumentgrows (or shrinks), without worrying to much about the detailed form. This is whattheO( )ando( ) Notation lets us functionf(n)is of constant order , or of order 1 when there exists somenon-zero constantcsuch thatf(n)c!1( )asn!1; equivalently, sincecis a constant,f(n)!casn!1. It doesn t matterhow big or how smallcis, just so long as there is some such constant. We then writef(n)=O(1)( )and say that the proportionality constantcgets absorbed into the bigO . Forexample, iff(n)=37, thenf(n)=O(1). But ifg(n)=37(1 2n), theng(n)=O(1) other orders are defined recursively. Sayingg(n)=O(f(n))( )meansg(n)f(n)=O(1)( )org(n)f(n)!c( )asn!1 that is to say,g(n)is of the same order asf(n), and they growat the same rate , or shrink at the same rate.
2 For example, a quadratic functiona1n2+a2n+a3=O(n2), no matter what the coefficients are. On the other hand,b1n 2+b2n 1isO(n 1).537538 Big-Omeans is of the same order as . The corresponding Little -omeans is ul-timately smaller than :f(n)=o(1)means thatf(n)/c!0 for any constantc. Re-cursively,g(n)=o(f(n))meansg(n)/f(n)= o(1), org(n)/f(n)!0. We also readg(n)=o(f(n))as g(n)is ultimately negligible compared tof(n) .There are some rules for arithmetic with big-Osymbols: Ifg(n)=O(f(n)), thencg(n)=O(f(n))for any constantc. Ifg1(n)andg2(n)are bothO(f(n)), then so isg1(n)+g2(n). Ifg1(n)=O(f(n))butg2(n)=o(f(n)), theng1(n)+g2(n)=O(f(n)). Ifg(n)=O(f(n)), andf(n)=o(h(n)), theng(n)=o(h(n)).These are notallof the rules, but they re enough for most :51 Friday 18thJanuary, 2013
