Algorithms: asymptotic complexity, big-O notation, big-Theta, big-Omega, small-o, small-omega

Опубликовано: 17 Декабрь 2020
на канале: Frank Stajano Explains

2,638

I teach Algorithms at the University of Cambridge. Through this channel I welcome anyone in the world to attend my lectures.

To assess and compare the performance of algorithms we need a more general metric than just the execution time, which would unhelpfully depend on the particular input and on the host computer. Instead, we abstract away many details and characterise the algorithm's running time in terms of a simpler function with a similar rate of growth. This is known as asymptotic complexity analysis. We define a few notations commonly associated with asymptotic analysis, such as big-Theta and big-O, as well as the less commonly used big-Omega, small-o and small-omega.

If you like my content, give it a thumbs up, subscribe to the channel and hit the notification bell to be notified of new videos. This will encourage me to produce more videos for the benefit of aspiring computer scientists. Feel free to comment below.

Course web page:
https://www.cl.cam.ac.uk/teaching/cur...

Course handout:
https://www.cl.cam.ac.uk/teaching/202...

My home page:
https://www.cl.cam.ac.uk/~fms27/