Sums, Approximations, and Asymptotics II you usually cant do much with it. It doesn' t readily cancel or combine with other terms In contrast, the expression on the right looks scary, but melds nicely into larger formulas So dont be put off: Stirlings Formula is your friend Stepping back a bit, Stirlings formula is fairly amazing. Who would guess that the product of the first n positive integers could be so precisely described by a formula involv ing both e and r?) If you re feeling a little crazy, you might pull out these even -more-precise bounds n)el(12n+1) These bounds are ridiculously close. For example, if n= 100, then we get 100 100!> V2007el/201 100!< 200re1/1200 The upper bound is less than 7 hundred-thousandths of 1% greater than the lower bound 3 Asymptotic Notation Our final topic is a special notation- called asymptotic notation- designed to sweep mathematical messes under the rug. Asymptotic notation is sort of like the Force from Star Wars. It's everywhere. Tts an essential part of the language of computer science And mostly it is a tool for good. At best, asymptotic notation suppresses irrelevant de- tails, while allowing the essential features of a mathematical analysis to shine through However, as we'll see, asymptotic notation also has an alluring dark side 3.1 Asymptotic Notation: The Jedi Perspective Suppose you want to know how long a computer takes to multiply two n x n matrices You could tally up all the multiplications and additions and loop variable increments and comparisons and perhaps factor in hardware-specific considerations such as page faults and cache misses and branch mispredicts and floating-point unit availability and all this would give you one sort of answer. (Whew! )Such an answer would be very accurate, but not very insightful. Given a very complicated formula for the running time, we would be hard-pressed to answer basic questions: How would doubling the size of the matrices alter th running time? What is the biggest matrix we can handle? Furthermore, a minor change in the procedure or hardware would invalidate the answer� � � �� � � �� � 8 Sums, Approximations, and Asymptotics II you usually can’t do much with it. It doesn’t readily cancel or combine with other terms. In contrast, the expression on the right looks scary, but melds nicely into larger formulas. So don’t be put off: Stirling’s Formula is your friend. (Stepping back a bit, Stirling’s formula is fairly amazing. Who would guess that the product of the first n positive integers could be so precisely described by a formula involv￾ing both e and π?) If you’re feeling a little crazy, you might pull out these even­more­precise bounds: n n n n 1/(12n+1) 1/(12n) √ 2πn � � e ≤ n! ≤ √ 2πn e e e These bounds are ridiculously close. For example, if n = 100, then we get: � �100 100! ≥ 100 √ 200π e 1/1201 e =1.000832... � �100 100! ≤ 100 √ 200π e 1/1200 e =1.000833... The upper bound is less than 7 hundred­thousandths of 1% greater than the lower bound! 3 Asymptotic Notation Our final topic is a special notation— called asymptotic notation— designed to sweep mathematical messes under the rug. Asymptotic notation is sort of like the Force from Star Wars. It’s everywhere. Tt’s an essential part of the language of computer science. And mostly it is a tool for good. At best, asymptotic notation suppresses irrelevant de￾tailss, while allowing the essential features of a mathematical analysis to shine through. However, as we’ll see, asymptotic notation also has an alluring dark side. 3.1 Asymptotic Notation: The Jedi Perspective Suppose you want to know how long a computer takes to multiply two n × n matrices. You could tally up all the multiplications and additions and loop variable increments and comparisons and perhaps factor in hardware­specific considerations such as page faults and cache misses and branch mispredicts and floating­point unit availability and all this would give you one sort of answer. (Whew!) Such an answer would be very accurate, but not very insightful. Given a very complicated formula for the running time, we would be hard­pressed to answer basic questions: How would doubling the size of the matrices alter the running time? What is the biggest matrix we can handle? Furthermore, a minor change in the procedure or hardware would invalidate the answer