Explore BrainMass

Proving O(log n) comparisons in key compaisons binary search

Prove that any binary search algorithm on a sorted array of size n that uses only key comparisons must require at least omega (log n) comparisons in the worst case.

Solution Preview

Suppose the sorted array is A with size n. That is A[1], A[2], ..., A[n].
According to the binary search, in the worst case, the root A[1] ...

Solution Summary

A binary search tree proof is provided.