Time & Space Complexity of Searching Algorithms

Linear Search

It is one of the most simple and straightforward search algorithms. In this, you need to traverse the entire list and keep comparing the current element with the target element. If a match is found, you can stop the search else continue.

Complexity Analysis

Time Complexity

• Best case - O(1) 
  The best occurs when the target element is found at the beginning of the list/array. Since only one comparison is made, the time complexity is O(1).
  Example - 
  Array A[] = {3,4,0,9,8} 
  Target element = 3 
  Here, the target is found at A[0].
   
• Worst-case - O(n), where n is the size of the list/array.
  The worst-case occurs when the target element is found at the end of the list or is not present in the list/array. Since you need to traverse the entire list, the time complexity is O(n), as n comparisons are needed.
   
• Average case - O(n)
  The average case complexity of the linear search is also O(n).

Space Complexity

The space complexity of the linear search is O(1), as we don't need any auxiliary space for the algorithm.

Read More About, Data Structures and Algorithms and Application of Graph in Data Structure

Binary Search

Binary search is a type of interval searching algorithm which works efficiently on sorted elements. It is a divide and conquers algorithm in which we compare the target element with the middle element of the list. If they are equal, then it implies that the target is found at the middle position; else, we reduce the search space by half, i.e. apply binary search on either of the left and right halves of the list depending upon whether target<middle element or target>middle element. We continue this until a match is found or the size of the array reaches 1.

Complexity Analysis

Time Complexity

• Best case - O(1)
  The best-case occurs when the target element is found in the middle of the original list/array. Since only one comparison is needed, the time complexity is O(1).
   
• Worst-case - O(logn)
  The worst occurs when the algorithm keeps on searching for the target element until the size of the array reduces to 1. Since the number of comparisons required is logn, the time complexity is O(logn).
   
• Average case - O(logn)
  Binary search has an average-case complexity of O(long).

Space Complexity

Since no extra space is needed, the space complexity of the binary search is O(1).

(See this Problem to test your understanding)

Read More - Time Complexity of Sorting Algorithms

Ternary Search

Like binary search, ternary search is also a kind of interval search algorithm that works on sorted arrays.

The only difference between binary and ternary search is we divide the array[l,r] into three parts in ternary search using two middle points, mid1 and mid2, where mid1 = l+ (r-l)/3 and mid2 = r - (r-l)/3. In each iteration, we ignore 2/3^rd of the search space and choose the interval in which the target element may lie - 

• Check if target==arr[mid1]. If true, then return as the search is successful. Else Check if target==arr[mid2], then return.
• If both the above conditions are false, then check if target<mid1 or target>mid2, if so then the search space becomes [l,mid1] and [mid2,r] respectively. 
• Else the search space chosen is [mid1,mid2]. 

The search is terminated when either the target element is found or the size of the search space becomes 1.

Complexity Analysis

Time Complexity

• Best case - O(1)
  The best-case occurs when the target element is found at mid1 or mid2. Since only two comparisons are needed at most, the time complexity is O(1).
   
• Worst-case - O(log₃n)
  The worst-case occurs when the ternary search continues until the size of the search space becomes 1. This can also happen when the target is not present in the array. So, the time complexity is O(log₃n).
   
• Average case - O(log₃n)
  The average case complexity of the ternary search is O(log₃n).

Space Complexity

Since no extra space is needed, the space complexity of the ternary search is O(1).

Also see Binary Search v/s Ternary Search

Jump Search

Jump search is a type of interval search algorithm that works on a sorted list of elements, and in each iteration, we skip a fixed number of elements called a block.

If you have an array A[] of size n, the block size B is generally set as B=√N for optimal performance.

The steps are - 

1. Check if A[0]==target. If yes, then the search is successful; else, if target > A[0], then move to the next block.
2. Similarly, check if A[B]==target. If true, it's a successful search else, if target > A[B], we move the next block starting from A[2B].
3. At any point in the process, if A[m*B]>target, then we perform a linear search from A[(m-1)*B] to A[m*B] to find the target element.

Complexity Analysis

Time Complexity

• Best case - O(1)
  The best-case occurs when the target is found at the beginning of the array. As we only perform one comparison, the time complexity is O(1).
   
• Worst-case - O(√N)
  The worst-case occurs when we need to perform a total of √N jumps which needs √N comparisons. Hence the time complexity is O(√N).
   
• Average case - O(√N)
  The average case complexity of the jump search is O(√N).

Space Complexity

Since no extra space is needed, the space complexity of the jump search is O(1).

Also see, Morris Traversal for Inorder.

Interpolation Search

The interpolation search algorithm is mainly used for searching an element in a uniformly distributed sorted list.

How to determine if the given data set is uniformly distributed or not?🤔

It is quite easy. If the difference between the consecutive elements in the list is consistent, then we can say that it is uniformly distributed.

If we are given an array A[low, high] and the target element is k, then the probable position of k is computed via the formula - 

Expected_position = low + (k - A[low])*(high-low)/(A[high]-A[low]) 

If A[Expected_position] = k, then search is successful, else if k>A[Expected_position] or k<A[Expected_position], then repeat the interpolation search on right part and left part of the array respectively until the target element is found or the size of the search space reduces to 0.

Complexity Analysis

Time Complexity

• Best case - O(1)
  The best-case occurs when the target is found exactly as the first expected position computed using the formula. As we only perform one comparison, the time complexity is O(1).
   
• Worst-case - O(n) 
  The worst case occurs when the given data set is exponentially distributed.
   
• Average case - O(log(log(n)))
  If the data set is sorted and uniformly distributed, then it takes O(log(log(n))) time as on an average (log(log(n))) comparisons are made.

Space Complexity

O(1) as no extra space is required.

Exponential Search

The exponential search consists of finding a possible range where the target element can be present and then performing a binary search over the found range. The algorithm starts with an array of size 1, and in each iteration, the size of the array is doubled, i.e. 1,2,4..so on until we find an index i for which A[i]>target. So, the possible range is [i/2,i]. 

Complexity Analysis

Time Complexity

• Best case O(1)
  The best-case occurs when the target is found exactly like the first position. As we only perform one comparison, the time complexity is O(1).
   
• Worst-case - O(logn)
  In the worst case, at most logn comparisons are made. So, the time complexity is O(logn).
   
• Average case - O(logn)
  The average case complexity of the jump search is O(long).

Space Complexity

O(1) as no extra space is required.

Check out this array problem - Merge 2 Sorted Arrays

Must Read Algorithm Types

Frequently Asked Questions

What does time complexity depend on?

The number of machine instructions that a program executes during its execution determines its time complexity in computer science.

What are the different types of time complexity?

The various types of time complexities can be Constant Time, Linear Time, Logarithmic, Polynomial, Quadratic, and Exponential.

Is interpolation search better than binary search?

Interpolation search works faster than binary search on the uniformly distributed sorted list because binary search always compares the target element to the middlemost element, but interpolation search finds the most probable position.

What are the two types of searching algorithms?

Sequential searching and interval searching.

Does an exponential search algorithm have an exponential complexity?

No, the time complexity of the exponential search is O(logn). The name exponential search implies that in every iteration, the number of steps by which the elements are skipped equals the exponent of 2.

Conclusion

In this article, we learned about various searching algorithms like linear search, binary search, ternary search, jump search, etc. We also saw their complexity analysis in terms of both time and space.

To strengthen your concepts of time and space complexity analysis, we have a curated list of blogs prepared for you to learn in one of the easiest and most intuitive ways - 

• Substitution Method
• Recursion Tree Method
• Design and Analysis of Algorithms
• Time & Space Complexity of Sorting Algorithms 
• Interesting Questions from (Substitution, Iteration, Recursion Tree, Master)
• Data Structure
   

Also Read About, floyd's algorithm

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests and some more Interview Experiences curated by top Industry Experts only on  Coding Ninjas Studio.