Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article at OpenGenus, we have presented the most insightful questions on Linear Search. One, often, consider Linear Search to be a simple algorithm and misses several points which are crucial to its performance and working. You must try these questions to make sure you understand Linear Search like a Algorithmic Researcher.

There are four options for each question out of which only one is correct. You will get multiple chances and once, you chose the correct answer, we will show you an explanation which will enable you to understand the key ideas deeper.

We have posed **14 most insightful questions on Linear Search**:

#### How many comparisons are done in Linear Search for N elements (in worst case)?

With optimizations, we can make n+1 comparisons in the worst case.

Check this article at OpenGenus to understand it better.

Before we go further into our other insightful questions on Linear Search, go through this pseudocode of Linear Search to refresh your knowledge:

```
boolean linear_search(data)
for i from 0 to length(data)
if search_data == data(i)
return true
return false
```

It, simply, goes through each element in the list and compares it with the search element. Let us know go into further questions.

#### What is the time complexity of Linear Search for string data?

To avoid this, one needs to convert the strings to corresponding hash values and then, proceed with linear search. With the modified version, the time complexity will be O(N).

References:

1. String hashing by OpenGenus

2. Rolling Hash by OpenGenus

3. Hash Map / Hash table by OpenGenus

#### What is the time complexity of Linear Search for Integer data?

#### Why is the worst case time complexity same as average case for Linear Search?

^{2}) considering 1st match, 2nd match and so on. This results in N cases which turns the average to be a function of N specifically O(N).

Hence, this is a result of sum of 1 to N is a function of N in order 2 (N

^{2}).

#### When is Hash Map preferred over Linear Search?

#### When is Linear Search preferred over Hash Map?

This is because Hash Map will have significant overhead for Memory allocation and preparation.

#### When is Linear Search preferred over Binary Search?

#### When is Binary Search preferred over Linear Search?

#### If list is sorted and you use Linear search, what can be the benefit?

Though this does not improve the time complexity but it improves the real time performance greatly.

#### When is Linear Search prefered over Interpolation Search?

So, if your list is small and distribution is not even (skewed), then Linear search is the way to go.

#### Can linear search be done on Linked Lists?

#### What is the best case time complexity for Linear Search?

#### Which search algorithm is best if data keeps changing frequently?

In some cases, Hash Map can be a good approach as well if the collisions are kept at minimum. If collisions are high, changing data set can make it more difficult.

#### Can linear search be made parallel for execution on multiple CPU cores?

This is important as other search algorithms like Binary search or Hash Map are difficult to be made parallel.

**Note**: There are several other types of search algorithms like Interpolation Search, Jump Search, Ternary Search and others. Linear search is the most basic approach and understanding it deeply opens door to several optimizations.