Great Ideas in Theoretical Computer Science: Time Complexity - Spring 2016

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.

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