Algorithm Design Approach

Below is a successful approach to algorithm design, the approach has lead to a golden age for algorithms. Helping steadily decrease the upper bounds for many important problems as well as uncover many known optimal algorithms.

Start

• Develop an algorithm
• Provide a lower bound

Gap?

• Look for new algorithm to lower the upper bound
• Raise the lower bound (more difficult )

Caveats

• Overly pessimistic to focus on worst case.
• Need better than “to within a constant factor” to predict performance.