Comparing algorithms based on their complexity

Given

An unsorted list of items

Objective

Find a given item in the list

Algorithmic choices

Linear Search

Traverse the unsorted list from the beginning to the end to find a given item. The complexity of this algorithm is O(n)

Binary Search

• In order to perform a binary search, we must first sort the list.
• To sort the list, we have to look at each element at least once hence we will at least have O(n). At best, we can compare and rearrange elements in log n time. Therefore, the sorting will be order of O(n log n)
• Once sorted, we can find the desired item in log n time using binary search.
• Therefore, the sort and search will be of order O(n log n + log n)

Comparison

Which algorithm performs better?

Let's say we want to search the list k times.

• Linear Search is O(k.n)
• Sort and Binary Search is O (n log n + k log n)

Conclusion

• If we were to search the list only once (k = 1), the Linear Search performs better.
• However, if we were to search the list multiple times (k > 1), the Sort and Binary Search solution works better.