The Complexity of Linear Search Algorithm
You have three different complexities faced while performing Linear Search Algorithm,
they are mentioned as follows.
1. Best Case
2. Worst Case
3. Average Case
Best Case Complexity
The element being searched could be found in the first position.
In this case, the search ends with a single successful comparison.
Thus, in the best-case scenario, the linear search algorithm performs O(1) operations.
Worst Case Complexity
The element being searched may be at the last position in the array or not at all.
In the first case, the search succeeds in ‘n’ comparisons.
In the next case, the search fails after ‘n’ comparisons.
Thus, in the worst-case scenario, the linear search algorithm performs O(n) operations.
Average Case Complexity
When the element to be searched is in the middle of the array, the average case of the
Linear Search Algorithm is O(n).
Next, you will learn about the Space Complexity of Linear Search Algorithm.
Space Complexity of Linear Search Algorithm:
The linear search algorithm takes up no extra space; its space complexity is O(n) for an
array of n elements.
Application of Linear Search Algorithm
The linear search algorithm has the following applications:
Linear search can be applied to both single-dimensional and multi-dimensional
arrays.
Linear search is easy to implement and effective when the array contains only a few
elements.
Linear Search is also efficient when the search is performed to fetch a single search
in an unordered-List.
Time and Space Complexity Analysis of Binary
Search Algorithm
Time complexity of Binary Search is O(log n), where n is the number of
elements in the array. It divides the array in half at each step. Space
complexity is O(1) as it uses a constant amount of extra space.
Aspect Complexity
Time Complexity O(log n)
Space Complexity O(1)
Best Case Time Complexity of Binary Search Algorithm: O(1)
Best case is when the element is at the middle index of the array. It takes
only one comparison to find the target element. So the best case complexity
is O(1).
Average Case Time Complexity of Binary Search
Algorithm: O(log N)
Consider array arr[] of length N and element X to be found. There can be
two cases:
Case1: Element is present in the array
Case2: Element is not present in the array.
There are N Case1 and 1 Case2. So total number of cases = N+1. Now
notice the following:
An element at index N/2 can be found in 1 comparison
Elements at index N/4 and 3N/4 can be found in 2 comparisons.
Elements at indices N/8, 3N/8, 5N/8 and 7N/8 can be found in 3
comparisons and so on.
Based on this we can conclude that elements that require:
1 comparison = 1
2 comparisons = 2
3 comparisons = 4
x comparisons = 2x-1 where x belongs to the range [1, logN] because
maximum comparisons = maximum time N can be halved = maximum
comparisons to reach 1st element = logN.
So, total comparisons
= 1*(elements requiring 1 comparisons) + 2*(elements requiring 2
comparisons) + . . . + logN*(elements requiring logN comparisons)
= 1*1 + 2*2 + 3*4 + . . . + logN * (2logN-1)
= 2logN * (logN - 1) + 1
= N * (logN - 1) + 1
Total number of cases = N+1.
Therefore, the average complexity = (N*(logN - 1) + 1)/N+1 = N*logN / (N+1)
+ 1/(N+1). Here the dominant term is N*logN/(N+1) which is approximately
logN. So the average case complexity is O(logN)
Worst Case Time Complexity of Binary Search Algorithm: O(log
N)
The worst case will be when the element is present in the first position. As
seen in the average case, the comparison required to reach the first element
is logN. So the time complexity for the worst case is O(logN).
Auxiliary Space Complexity of Binary Search
Algorithm
The auxiliary space complexity of the Binary Search Algorithm is O(1),
which means it requires a constant amount of extra space regardless of the
size of the input array. This is because Binary Search is an iterative
algorithm that does not require any additional data structures or recursion
that grows with the input size. Although, we can also implement Binary
Search recursively.
