Time Complexity

This lecture introduces time complexity by analyzing running time as input size grows. It uses palindrome algorithms and computational models to explain asymptotic behavior, polynomial and exponential time, brute force, and intrinsic complexity.

Syllabus

Intro
Dammit I'm mad, by Demetri Martin
Suppose you are the proofreader. How would you check if there's a mistake?
Problems
Algorithms
Instance/input size
When instances are integers
When instances are lists/strings
When instances are graphs
Measuring running time
Running time example
Why worst case?
On input I, algorithm A takes 2718 steps
Run time scaling
Let's do a log-log plot Say 1 step = 1 us
Intrinsic complexity
PALINDROMES: We know an O(n) algorithm, TwoFingers. Could there be a faster one? E.g., O(n)?
MULTIPLICATION
Common progress paradigm for a problem
Does "polynomial time" imply "efficient"?
Definition recall(?)