Sequential (Linear) Search

Introduction to Linear Search

Linear search, also known as sequential search, is a simple searching algorithm that checks each element of a list in order until a match is found or the entire list has been traversed.

Algorithm Steps

 

1. Start at the beginning of the list.

1. Compare the target value with the current element.

1. If the target value matches the current element, the search is successful and the position of the element is returned.

1. If the target value does not match the current element, move to the next element in the list.

1. Repeat steps 2-4 until a match is found or the end of the list is reached.

 

 

None

Time & Space Complexity

Time complexity – O(n)

Because linear search potentially needs to check each item (n) in the list once in the list, the time complexity is O(n)

Space complexity O(1)

The space complexity of a linear search algorithm is generally O(1), which means it uses a constant amount of additional memory regardless of the size of the input data. This is because a linear search does not require any additional data structures or memory allocation that scales with the size of the input.

You may use a few variables for control and temporary storage, but the memory usage remains constant and doesn’t depend on the size of the input data.

Pros and Cons of Linear Search

Advantages

• Simple and easy to understand
• Works on both sorted and unsorted lists
• Works well for small data sets
• Useful if you expect the item to be near the beginning of the list

Disadvantages

• Inefficient for large data sets
• Time complexity: O(n), where n is the size of the list
• Can be slow compared to other search algorithms