Suppose you are looking for an element x in a sorted array of n elements. Prove that the algorithm requires \( O(logn) \) comparisons.
\( O(logn) \) comparison means the maximum number of comparison to perform the algorithm would be logn . To find an element x in a sorted list of n elements we can perform binary search (since the given array is sorted). If we put the sorted array in a tree the height of the tree would be logn . To find an element x we have to traverse along the entire height of the tree from root to leaf until the element is found and perform comparison at each step with the element we are looking for. Thus the maximum number of comparison would be logn . |