Navigation
Understanding why some algorithms are better than others for specific tasks.
If you had to find a single name in a phonebook with 1,000,000 people, would you start at page one and read every name? Or is there a 'cheat code' to find it in just 20 steps?
In computer science, efficiency isn't about how fast a computer's motor runs. Instead, it's about the number of operations (steps) an algorithm takes to finish a task. Imagine two chefs making a pizza. Chef A takes 50 steps, while Chef B takes only 10 steps to make the exact same pizza. Chef B is more efficient! We measure this because computers have limited time and energy. If an algorithm takes steps to process items, we can predict how long it will take as the pile of data grows larger.
Quick Check
In computer science, how do we measure the 'efficiency' of an algorithm?
Answer
By counting the number of operations or steps it takes to complete a task.
The simplest way to find something is a Linear Search. You start at the beginning and check every single item until you find what you're looking for. If you have a list of items, and the item you want is at the very end, the computer has to perform operations. This is easy to program, but it gets very slow if you have millions of items! We say the 'worst-case scenario' for a list of size is simply steps.
1. You have a drawer with individual socks. 2. You are looking for the one blue sock. 3. In a Linear Search, you pull out socks one-by-one. 4. If the blue sock is the last one you grab, you performed operations. 5. Math: For , steps = .
A Binary Search is much faster, but it has one rule: the list must be sorted (like a dictionary or a numbered list). Instead of checking one-by-one, you jump to the middle. If your target is higher than the middle, you throw away the bottom half. You keep dividing the list in half until you find the target. This 'divide and conquer' strategy is incredibly powerful. For a list of items, the number of steps is roughly .
1. I am thinking of a number between and . 2. You guess the middle: . I say 'Higher'. (You eliminated through in one step!) 3. You guess the middle of the remaining (-): . I say 'Lower'. 4. You guess the middle of -: . I say 'Correct!' 5. It only took steps to find a number out of possibilities. Using Linear Search, it could have taken steps!
Quick Check
What is the main requirement for a Binary Search to work on a list?
Answer
The list must be sorted (in order).
Why does this matter? For small lists, the difference is tiny. But as gets bigger, the gap becomes massive. If , a Linear Search takes steps. A Binary Search takes only about steps! Choosing the right algorithm is the difference between a program that feels 'instant' and one that freezes your computer.
Scenario: You are designing a search bar for a music app with songs (). 1. If the songs are unsorted, you must use Linear Search. Steps: . 2. If you sort the songs alphabetically first, you can use Binary Search. 3. Binary Search steps: steps. 4. Conclusion: Sorting the data first allows you to use a much more efficient algorithm for large datasets.
If an algorithm takes 5 steps for 5 items and 100 steps for 100 items, what type of search is it likely using?
Which algorithm is most efficient for finding a name in a sorted list of 1,000,000 entries?
True or False: A Binary Search will always work, even if the list is in a random order.
Review Tomorrow
Tomorrow, try to explain to a friend why a dictionary is easier to use than a pile of random papers using the word 'efficiency'.
Practice Activity
Play the 'Higher or Lower' game with a family member using numbers 1-100. See if you can always find their number in 7 guesses or less using the Binary Search method!