Big O, Omega, and Theta
Abdul Bari, about 20 minutes. This is the formal definition with the constant \(c\) and the starting \(n_0\), which is the version to be able to say out loud.
Watch
Short lectures for the ideas, and one sandbox if you want a different picture than the one on this site.
Watch these after the note, not instead of it. The course’s indexing, the <= tie, and the exact meaning of \(t_j\) are in the notes. A general lecture will not use those conventions.
The same idea, said with a phone book
CS50, 9 minutes. Linear search, binary search, and why best case and worst case get different symbols. Use it to hear \(\Theta\) said next to a search, then come back to the shelf on the Cases page.
Insertion sort in two minutes
Michael Sambol. Watch the sorted region grow by sliding, then step the same idea on the Sorts page and count \(t_j\).
Selection sort in three minutes
Michael Sambol. Watch the minimum get swapped to the wall. His comparison may be strict. Yours is <=, so a tie moves the index right. That difference is an exam point.
If you want another picture
VisuAlgo’s sorting page will animate both algorithms on an array you type. Use it to see motion. Use this site’s stepper when you need the course’s indexing, the test count, and the invariant sentence.
Abdul Bari’s shorter clip on counting loop bodies is Time Complexity #1. It is the triangle sum, said at a board.