Number of comparisons to find an element in a sorted array
  • sortedarray
  • array
  • searching
  • noOfComparisons
  •   
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (4855)

Suppose you are looking for an element x in a sorted array of n elements. Prove that the algorithm requires \( O(logn) \) comparisons.


Posted Answers

\( 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 .

e.g, for a sorted array of length 16 we need maximum \( log_{2}16\ i.e , 4 \) comparisons to find a specific element.

You need to Sign In to post your solution.