What does it mean for an algorithm to run in O(log n), O(n), or O(n²) time, and why does it matter? Professor Yun William Yu (Carnegie Mellon University) gives a crash course in Big-O notation, the language computer scientists use to compare how running times grow as inputs get larger.
He starts with binary search, the classic example of where log n comes from: every step cuts the list in half, so even a million items take only about twenty steps. Then he works through O(n) and O(1) by example, runs a live vote on how many jumps binary search needs to find a number, and finishes with O(n²), the cost of comparing every pair of items from two lists. By the end you will be able to read a running time and know how an algorithm will scale.
About the instructor:
William’s YouTube channel:
This lesson comes from Episode 3 of Algorithms, a free live course on Philomath.
Take the whole course free:
Watch the full Episode 3 livestream:
Every lesson in order:
More free courses at the intersection of science, AI, and computer science:
Chapters:
0:00 A crash course in Big-O, from O(1) to O(n²)
3:43 Binary search: where log n comes from
9:16 O(n) and O(1), by example
11:22 A vote: how many jumps to find 26?
14:13 O(n²): every pair from two lists
#algorithms #datastructures #computerscience
source
Thank you so much for explaining the big(O) notation very clearly!