6.042/18.] Mathematics for Computer Science March 10. 2005 Srini devadas and Eric Lehman Lecture notes Sums and Approximations When you analyze the running time of an algorithm, the probability some procedure succeeds, or the behavior of a load-balancing or communications scheme, you'll rarely get a simple answer. The world is not so kind. More likely, you'll end up with a complicated sum 1+ Or you might get an answer that is just tad too complicated to grasp intuitively And these examples are relatively benign! So the ability to cope with such messy mathematical expressions is an important skill in computer science-and in many other areas of science and engineering. This might not seem glorious, but people who can cut monstrous expressions down to size in moments can seem pretty amazing to the uninitiated. This week, we'll equip you with the most seful tricks of the trade 1 The value of an annuity Would you prefer a million dollars today or $20,000 a year for the next fifty years? This is a question about the value of an annuity, a financial instrument that pays out a fixed amount of money at the beginning of every year for some specified number of years In particular, an n-year, Sm-payment annuity pays m dollars at the start of each year for n years. In some cases, n is finite, but not always. Examples include lottery payouts student loans, and home mortgages. There are even Wall Street people who specialize in trading annuities For many reasons, $20,000 a year for 50 years is worth much less than a million dollars ght now. For example, consider the last $20,000 installment. If you had that $20,000 right now, then you could start earning interest, invest the money in the stock market,� � 6.042/18.062J Mathematics for Computer Science March 10, 2005 Srini Devadas and Eric Lehman Lecture Notes Sums and Approximations When you analyze the running time of an algorithm, the probability some procedure succeeds, or the behavior of a load­balancing or communications scheme, you’ll rarely get a simple answer. The world is not so kind. More likely, you’ll end up with a complicated sum: �n 1 k + √ k k=1 Or a nasty product: � � � � � � � � 1 2 3 n 1 + 1 + 1 + 1 + n n n 2 2 2 2 · · · n Or you might get an answer that is just tad too complicated to grasp intuitively: 72/n n 1 + 100 And these examples are relatively benign! So the ability to cope with such messy mathematical expressions is an important skill in computer science— and in many other areas of science and engineering. This might not seem glorious, but people who can cut monstrous expressions down to size in moments can seem pretty amazing to the uninitiated. This week, we’ll equip you with the most useful tricks of the trade. 1 The Value of an Annuity Would you prefer a million dollars today or $20,000 a year for the next fifty years? This is a question about the value of an annuity, a financial instrument that pays out a fixed amount of money at the beginning of every year for some specified number of years. In particular, an n­year, $m­payment annuity pays m dollars at the start of each year for n years. In some cases, n is finite, but not always. Examples include lottery payouts, student loans, and home mortgages. There are even Wall Street people who specialize in trading annuities. For many reasons, $20,000 a year for 50 years is worth much less than a million dollars right now. For example, consider the last $20,000 installment. If you had that $20,000 right now, then you could start earning interest, invest the money in the stock market