Lesson 1.3: Asymptotics Reprise
Class Meeting:
| Section | Slides | Annotated Slides | Video |
| 12–1PM | 1.3-asymptotics-analysis-203-1221.pdf Download 1.3-asymptotics-analysis-203-1221.pdf | PDF Download PDF |
Available now on Zoom Cloud Recordings |
| 1–2PM | 1.3-asymptotics-201-1pm.pdf Download 1.3-asymptotics-201-1pm.pdf | 1.3-asymptotics-201-1pm-1.pdf Download 1.3-asymptotics-201-1pm-1.pdf |
Available now on Zoom Cloud Recordings |
| 4–5PM | 1.3-asymptotics-201-4pm.pdf Download 1.3-asymptotics-201-4pm.pdf | 1.3-asymptotics-201-4pm-1.pdf Download 1.3-asymptotics-201-4pm-1.pdf |
Available now on Zoom Cloud Recordings |
Readings:
- Carrano & Henry : Chapter 10
- Epp : Chapter 11.2 - 11.3
- Zych C++ intro.pdf
Summary:
This lesson provides a quick review of "asymptotics" from cpsc121. After reminiscing about the definition of big-O, we give additional useful asymptotic definitions and demonstrate a compelling and surprising result. Finally, we conclude with a small example of how asymptotics are used in algorithm runtime characterization.
Learning Outcomes:
Upon completion off this lesson, students will be able to:
- explore the differences between best, average, and worst case analysis
- report the definitions of big-O, big-Omega, and big-Theta.
- remember how to do a proof of T(n) = O(f(n)) (from 121)
- apply big-O analysis to very simple code