1.
Introduction
2.
Types of Searching Algorithms
2.1.
Sequential Search
2.2.
Interval Search
3.
Linear Search
3.1.
Complexity Analysis
4.
Binary Search
4.1.
Complexity Analysis
5.
Ternary Search
5.1.
Complexity Analysis
6.
Jump Search
6.1.
Complexity Analysis
7.
Interpolation Search
7.1.
Complexity Analysis
8.
Exponential Search
8.1.
Complexity Analysis
9.
9.1.
What does time complexity depend on?
9.2.
What are the different types of time complexity?
9.3.
Is interpolation search better than binary search?
9.4.
What are the two types of searching algorithms?
9.5.
Does an exponential search algorithm have an exponential complexity?
10.
Conclusion
Last Updated: Mar 27, 2024

# Time & Space Complexity of Searching Algorithms

Yukti Kumari
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## Introduction

Searching is a part of our day-to-day life. Isnâ€™t it? It is something we all have used at some point in our life, be it searching for books in a library or chapters in a book or using various search engines.

The most intuitive example is searching for a particular topic online. Basically, we search or filter out the desired data from a bunch of information stored in the databases. So, there has been continuous improvement in searching algorithms to make them more efficient and real-time by minimizing the search time.

In this article, we will learn about the different searching algorithms and analyze their time and space complexity

Let's see the table below to get an idea of all the searching algorithms and their time complexity as well as space complexity which we will discuss in detail in the coming sections -

Also see, Longest Common Substring and Rabin Karp Algorithm

## Types of Searching Algorithms

Broadly speaking, there are two types of searching algorithms -

• Sequential Search
• Interval Search

### Sequential Search

The algorithm in which all the elements of a dataset are checked sequentially until a match is found irrespective of the order of elements is called sequential search.
E.g. - Linear search

### Interval Search

The algorithm in which only certain parts of the dataset are checked for the target element based on the order of elements(like ascending or descending) is called interval search.
E.g.- Binary search

From the next section onwards, we will see each of the searching algorithms one by one with their complexity analysis and examples to comprehend the concepts easily.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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/3rd 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(log3n)
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(log3n).

• Average case - O(log3n)
The average case complexity of the ternary search is O(log3n).

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

### 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 -