Question

Discuss the various Searching algorithms and their respective algorithm complexities.

Answer 1

Solution:

There are many searching algorithms some of them are listed below-

(1) Linear search

(2) Binary search

(3) Exhaustive search or Brute force search

Discussing Linear search:

=>In the linear search if we have an array of n elements and we want to search a key k in the array then we have to search all the elements of array linearly starting from the first element of array to the last element of the array to find the key element k.

Time complexity:

=> Best case: In best case key element can be found at the first index or nearest to the first index of the array so the time complexity = O(1)

=> Worst case: In worst case key element can be found at the last index or nearest to the last index of the array or might be the case key element may not be present even after searching all the elements of the array so in that case time complexity = O(n)

=>Average case: Average case will be the average of above two cases so, in that case, time complexity = O(n)

Discussing the binary search:

=>The primary requirement of binary search is that the array must be sorted.

=>When we search any key element k in the sorted array of n elements then we follow the sequence by first searching in the middle and if key element is less than the middle element then we will search in the middle of the left part of the middle of the whole array and so on.

Time complexity:

=>Best case: The best case will be when the key element k can be found in the middle of the whole array so in that case time complexity will be = O(1)

=>Worst case: The worst case will be when the key element k can be found in the last iteration of this procedure or may not be found in the whole array so in that case time complexity will be = O(log(n))

=> Average case: The average case will be the average of above two cases so, in that case, time complexity will be = O(log(n))

Discussing exhaustive search:

=> Exhaustive search means trying every possible combination to reach the desired goal.

Time complexity:

=> In exhaustive search time complexity = O(2n)

I have explained some of the searching algorithms.