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.
Overview
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(?)
Taught by
Ryan O'Donnell
Related Courses
-
Great Ideas in Theoretical Computer Science: Time Complexity - Spring 2016
-
Data Structures and Algorithms with Visualizations – Full Course (Java)
-
How to Calculate Time Complexity with Examples - Part 1
-
Art of C Programming
-
Time Complexity of Loops - Solved Problem 5
-
Time Complexity of Loops - Solved Problem 4
