Today we’ll review and play with asymptotic analysis. These notes will have a different feel, as we’re not solving an algorithmic problem but performing analysis on algorithms (or, in some cases, performing bits and pieces of that analysis).
A few notes:
- Here are today’s notes on asymptotic analysis.
- Here is a handout describing little-o and little-ω notation.
- Read Section 3.1 of the textbook introducing graphs. (But, no pre-class quiz for Wednesday.)
- The add/drop deadline is Tue 20 Jan. (We’d love to have you stay, but if you intend to drop, don’t miss the deadline!)
- Fill out the optional start-of-term survey (by the add/drop deadline tomorrow!) to help me learn a bit more about you and help the department learn about our courses. It’s worth 2 bonus points!
- Today’s pre-class quiz went OK with some hiccoughs:
- Functions like lg n and n lg n are within the class of “polynomial” functions as far as we’re concerned (because they’re upper-bounded by a polynomial).
- Linear functions (like the simplest one: n) are definitely in the class “polynomial”!
- If you thought it takes O(5^n) time to investigate all subsets of size 5 of a set of size n, be sure to read the chapter!