Data Structures and Algorithms - Sorting and Searching

2. The time complexity of the linear search algorithm over an array of n elements is

  • Option : B
  • Explanation : Linear search has linear-time complexity; binary search has log-time complexity. Here is a table that provides some intuition about the running speeds of algorithms Logarithmic: Linear: array size | N -------------------------------------------------------- 8 | 8 128 | 128 256 | 256 1000 | 1000 100,000 | 100,000 .... Binary search and other divide-and-conquer algorithms have logN time complexity; we say O(logN) Linear search has linear time complexity: O(N). So the option is 'B'
Cancel reply
Cancel reply