Try these questions if you think you know Linear Search

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

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)?

2 * N + 1

N + 1

2 * N

In a simple implementation, linear search algorithm takes 2*N + 1 comparisons where N comparisons are to check if target element is found and N+1 comparisons are to check if end of list is reached in the 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?

O(N^2)

O(N)

O(N logN)

O(log N)

The key idea in this question is that comparing two strings of length N takes O(N) time. Hence, to compare N strings, it will take O(N^2) time.

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?

O(N)

O(N^2)

O(1)

O(N logN)

The idea is that comparing two integers take constant O(1) time so the time complexity of O(N) is maintained. After going through the previous question, you will find it easy to understand this.

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

small cases are function of N

worst case has more weightage

Frequency of data

Occurrence of prime numbers

This is because when we sum up all cases, we get a function of N more specifically O(N²) 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²).

When is Hash Map preferred over Linear Search?

Large dataset

Unordered dataset

Sorted dataset

Small dataset

Using Hash map will give a significant performance boost over Linear Search if the dataset is large. This is because if the dataset is small, then a large amount of memory is reserved but not used in case of Hash Map which results in high memory allocation. Linear search is simple and should be the choice for small dataset.

When is Linear Search preferred over Hash Map?

Small dataset

Unordered dataset

Sorted dataset

Large dataset

Linear search should be used in place of Hash Map if the dataset is small. Even though the time complexity of Linear Search O(N) will be more than that of Hash Map (1) but the real time performance will be better.

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

When is Linear Search preferred over Binary Search?

Unsorted dataset

Sorted dataset

Large dataset

Small dataset

This is simple as if the data is unsorted then there is no option to use Binary Search. Sorting it beforehand will be an overhead and sorting takes significantly more time than a simple linear traversal.

When is Binary Search preferred over Linear Search?

Sorted dataset

Unsorted dataset

Large dataset

Small dataset

When data is sorted, linear search should not be considered as Binary Search will perform better. This is because in Binary Search we can simply eliminate checking most of the elements irrespective of other factors.

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

Find absence quickly

List iteration not needed

Multiple searches at a time

No benefit

If the list is sorted and you are using linear search, then if the current element is larger than the search element (if list is in ascending order), then we can establish that the search element is not present.

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

When is Linear Search prefered over Interpolation Search?

Distribution is skewed

Normal distribution

Same frequency

Gaussian distribution

Interpolation search works best if the distribution of the elements is even so that the location of the search element can be predicted. Moreover, it needs the data to be sorted which is an overhead.

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?

Yes

Depends on data

Depends on language

The basic operation of Linked List is linear traversal which is done perfectly in Linked Lists. The problem arises in other search algorithms like Binary Search.

What is the best case time complexity for Linear Search?

O(1)

O(N)

O(N^2)

O(log N)

The best case happens when the first element in the list is same as the search element and in this case, the search is terminated just after the first comparison. Hence, it takes constant time O(1) in the best case.

Which search algorithm is best if data keeps changing frequently?

Linear Search

Binary Search

Interpolation Search

Hash Map

If the data set keeps changing frequently, then Linear Search is the best approach. For other approaches, maintaining the new structure for the changing data set is an overhead and hence, will result in lower performance.

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?

Yes

Only for Integer

Only on GPU

Linear search can run on multiple CPU cores as the data set can be divided equally among the cores where the search will continue as usual. If the search element is found in any core, all cores terminate the search process.

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.