Completed
When instances are integers
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Time Complexity
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Dammit I'm mad, by Demetri Martin
- 3 Suppose you are the proofreader. How would you check if there's a mistake?
- 4 Problems
- 5 Algorithms
- 6 Instance/input size
- 7 When instances are integers
- 8 When instances are lists/strings
- 9 When instances are graphs
- 10 Measuring running time
- 11 Running time example
- 12 Why worst case?
- 13 On input I, algorithm A takes 2718 steps
- 14 Run time scaling
- 15 Let's do a log-log plot Say 1 step = 1 us
- 16 Intrinsic complexity
- 17 PALINDROMES: We know an O(n) algorithm, TwoFingers. Could there be a faster one? E.g., O(n)?
- 18 MULTIPLICATION
- 19 Common progress paradigm for a problem
- 20 Does "polynomial time" imply "efficient"?
- 21 Definition recall(?)
