Example: Searching

Example: Searching

• Assume List is Ordered
• Comparisons of the Form: KeyFor all x, 0Decision Tree for ANY Search Algorithm Must have at least n vertices
• Property of Trees: Any binary tree with n vertices must have height at least lg n

Previous slide

Next slide

Back to the first slide

View Graphic Version