[MINI] Big Oh Analysis

Linear Search

Linear search is a straightforward algorithm where each element is checked one by one until the desired item is found. Kyle Polich illustrates this with a deck of cards, explaining that to find two queen of hearts, one must examine each card, making the process linear in time complexity 1. This means if the deck size triples, the time taken to search also triples. Similarly, checking if all items on a grocery list are in a cart involves comparing each list item with the cart's contents, resulting in a time complexity of N squared 2. Polich emphasizes that while small optimizations might slightly improve speed, they don't significantly alter the algorithm's overall efficiency.

   

Binary Search

Binary search offers a more efficient alternative to linear search by dividing the search space in half with each step. Kyle Polich explains that this method is ideal for sorted data, such as finding a word in a dictionary, where the search time is logarithmic 3. Unlike linear search, which requires checking each element, binary search quickly narrows down the possibilities, significantly reducing the time needed. Polich notes that while some tasks, like searching a deck of cards, can't benefit from this method without additional processing, binary search remains a powerful tool for efficiently handling large datasets.