Theory of Algorithms

Most algorithms would have a best, average and worst case type of analysis.

Best Case

• Determined by the “easiest” input.
• Goal for all inputs. Worst Case
• Determined by the most “most difficult” input.
• Provides a guarantee for all inputs. Average Case
• Need a model for “random” input.
• Provides a way to predict performance.

3-Sum Determined by Algorithm analysis

For a brute force all three would be the same:

• ~$\frac{1}{2} N^{3}$

Compared to a Binary Search:

• Best Case ~1
• Average ~lg N
• Worst ~lg N

Approaching Algorithm Design through Analysis

• Understand our input to effectively process it.
• Approach 1: design for the worst case
• Approach 2: randomize, depend on a probabilistic guarantee.

Goals

• Establish the “difficulty” of a problem.
• Develop “optimal” algorithms

Approach

• Suppress details in analysis: Analyse ” to within a constant factor”
• Eliminate variability in input models by focusing on the worst case

Optimal Algorithm

• Performance guarantee (to within a constant factor) for any input.
• No Algorithm can provide a better performance guarantee.