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(?)
Description:
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.