Algorithms Lecture 3: Asymptotic Complexity (Part 2) - California State University, Sacramento Spring 2018

California State University, Sacramento
Spring 2018
Algorithms
by Ghassan Shobaki

Worksheet 1.1 video
https://www.youtube.com/watch?v=reD6hRJSCWc&list=PL6KMWPQP_DM-KNuLShWmdXbmP1MnzXcuq&index=1&t=17s

Text book: Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, 3rd Edition, MIT Press, Cambridge (2009)


Correction:
At 1:11:05: In the limit on the second line (the one for comparing a polynomial with an exponential), the parentheses must be deleted and a limit (as n goes to infinity) must be added after the equality sign. That's because L' Hospital's Rule tells us that the limit of the ratio between two functions is equal to the limit of the ratio between their derivatives; it does not say that the ratios themselves are equal.