Exploring Time and Space Complexities of Linear Search

Linear search is a simple algorithm that searches for an element in an array or list by checking each element one by one from the start until:

• the target element is found, or
• the end of the list is reached.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

template<typename T>
int linear_search(const vector<T>& arr, const T& target) {
    for(int i = 0; i < arr.size(); ++i) {
        if(arr[i] == target) {
            return i;
        }
    }
    return -1;
}

Best Case Time Complexity: O(1)

The best case time complexity occurs when the target element is found at the first position of the list. For example,

arr = 5, 10, 20, 40
target = 5

Here, the target element 5 is found immediately, resulting in a time complexity of O(1).

Worst Case Time Complexity: O(n)

The worst case time complexity occurs when the target element is either not present or at the last position in the list. For example,

arr = 5, 10, 20, 40
target = 40

Here, the algorithm has to search through the entire list, resulting in a time complexity of O(n).

Average Case Time Complexity: O(n)

In the average case, the target element is somewhere in the middle of the list, requiring the algorithm to check approximately half of the elements.

Hence, the average case time complexity is O(n).

Space Complexity of Linear Search: O(1)

Linear search is an in-place algorithm that does not require additional memory (apart from a few variables like i for indexing and target for comparison).

Therefore, the space complexity of linear search is O(1).

Summary: Time and Space Complexity

When to Use Linear Search?

When to Use:

1. Small Datasets: Linear search is ideal when the dataset is small or unsorted.
2. Unstructured Data: Use linear search when data is stored in an unstructured format or as a list, and more advanced search algorithms, like binary search, are not applicable.

When Not to Use:

1. Large Datasets: In such cases, resort to faster search algorithms such as binary search (if the data is sorted) or hash tables for constant-time lookups.