Chapter 1 of 12: Before the lecture
Bell times linear search, binary search and a nested-loop diameter function in Python, then formalizes their growth.
Big Oh and Theta notation describe how an algorithm's running time grows with input size, independent of any particular machine. In session 21 of MIT's introductory Python course, Bell starts by timing functions with Python's performance counter. Linear search, binary search, the built-in in operator and a nested-loop diameter function on 2D points show sharply different scaling. Counting operations then yields a formula in input size, and worst-case asymptotic analysis keeps only its dominant term. Bell defines as an upper bound and as a tight bound, states the laws of addition and multiplication, and surveys classes from constant to exponential.
Big Oh and Theta notation describe how an algorithm's running time grows with input size, independent of any particular machine. In session 21 of MIT's introductory Python course, Bell starts by timing functions with Python's performance counter. Linear search, binary search, the built-in in operator and a nested-loop diameter function on 2D points show sharply different scaling. Counting operations then yields a formula in input size, and worst-case asymptotic analysis keeps only its dominant term. Bell defines as an upper bound and as a tight bound, states the laws of addition and multiplication, and surveys classes from constant to exponential.

This lecture
Lecture 21 of 25 of Introduction to Computer Science and Programming using Python.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in