Potential Function Analysis (6b)
Michael L. Littman
September 17th, 1998
METHODS OF ANALYSIS
Language-Oriented Analysis
Return to Russia
Recursive
The While Version
Dealing with while loops
POTENTIAL FUNCTION ANALYSIS
Motivation
In-Place Permutation Sorting
An Algorithm
Empirical Observation
Intuitive Analysis
Potential Function Basics
Amortized Cost
Fundamental Potential Function Inequality
Using the Inequality
Analysis of Permutation Problem
Punch Line
EXAMPLES
While in Russia...
Quicksort Pivot
Web Walk
Next:
METHODS OF ANALYSIS
