Estimated Time

10 minutes

Learning Objectives of this Module

In this module, we will learn how to analyze the running time and auxiliary space requirements of Linear Search and Binary Search.

In particular, we will:

• Understand the amount of work performed during one iteration of a search.
• Extend the analysis to an array containing $N$ elements.
• Understand why Linear Search has a worst-case time complexity of $O(N)$.
• Understand why Binary Search has a worst-case time complexity of $O(\log N)$.
• Compare the auxiliary space requirements of iterative Linear Search and iterative Binary Search.
• Understand the additional preprocessing cost of sorting an unsorted array before applying Binary Search.
• Compare the total cost of different searching strategies when one or multiple searches are performed on the same array.