Time Complexity

Learn about time complexity in algorithms through this comprehensive 1-hour 12-minute lecture. Explore various aspects of algorithmic efficiency, including problem types, input sizes, measuring running time, and worst-case scenarios. Delve into intrinsic complexity, palindrome algorithms, and multiplication techniques. Examine the concept of polynomial time and its implications for efficiency. Gain insights into common progress paradigms for problem-solving and enhance your understanding of algorithmic analysis.

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(?)