Explore time complexity in theoretical computer science through this comprehensive lecture from CMU's "Great Ideas in Theoretical Computer Science" course. Delve into the concept of running time, focusing on worst-case scenarios and the formal definition of O(n?) notation. Examine common run-time scaling patterns and their representation on log-log plots. Learn about intrinsic complexity and its implications for algorithm design. Gain insights from practical examples, including the analysis of a Palindrome Turing Machine. Understand the significance of time complexity in evaluating algorithm efficiency and performance across various input sizes.
Great Ideas in Theoretical Computer Science: Time Complexity - Spring 2016
Overview
Syllabus
Intro
In 1993, noted comedian Demetri Martin took a math course at Yale called Fractal Geometry.
Running time of deciding PALINDROME
Instance/input length
Defining running time
Why worst case?
Our Palindrome TM had running time
INFORMAL Definition
Examples
Formal definition of O(n?)
Common run-time scaling
A log-log plot Say 1 step = 1 us
Intrinsic complexity
Taught by
Ryan O'Donnell
