Introduction to Evaluating Algorithms
In Computer Science, there is often more than one way to solve a problem. Think of it like tidying your bedroom: you could throw everything into the cupboard (fast, but messy), or you could fold every item perfectly (slow, but organized). Both get the room "tidy," but they have different levels of efficiency.
When we evaluate an algorithm, we aren't just checking if it works. We are looking at how well it performs and whether it is the "best" tool for the job. In this chapter, we focus on how to judge an algorithm's fitness for purpose and its efficiency.
Note: To understand these evaluations, you should already be familiar with the standard searching and sorting algorithms (Linear Search, Binary Search, Bubble Sort, and Merge Sort).
1. Fitness for Purpose
Before looking at speed, we must ask: Does the algorithm actually do what it is supposed to do? An algorithm that is incredibly fast but gives the wrong answer is useless!
To evaluate fitness for purpose, we check it against:
• Requirements: Does it meet all the specific needs of the user? (e.g., if the user needs the data sorted alphabetically, does the algorithm do that?)
• Logical Reasoning: Does the logic of the algorithm hold up? Is it sound, or are there "edge cases" where it might break?
• Test Data: We run the algorithm using normal, boundary, and erroneous data to see if it produces the correct output. If an algorithm fails to handle a specific type of data, it is not fit for purpose.
2. Understanding Efficiency
Efficiency usually refers to how many resources an algorithm uses. We primarily look at two types:
A. Time Efficiency
This is a measure of how long an algorithm takes to complete. Instead of measuring in seconds (which depends on how fast the computer's CPU is), we measure efficiency by counting the number of steps or operations the algorithm performs.
As the amount of data (let's call the number of items \( n \)) increases, some algorithms stay fast, while others become very slow.
B. Space Efficiency
This refers to how much memory (RAM) the algorithm needs while it is running. Some algorithms are "in-place" (they don't need much extra room), while others need to create copies of the data, which uses up more space.
3. Comparing Standard Algorithms
The choice of algorithm is heavily shaped by the data structures and the values we are dealing with. Here is how the standard algorithms compare:
Searching Algorithms
• Linear Search: This checks every item one by one. If you have \( n \) items, it might take \( n \) steps. It is simple but becomes inefficient as the list grows. However, it has one big advantage: the data does not need to be sorted.
• Binary Search: This is much more efficient because it halves the search area each time. For a list of 1,000 items, a linear search might take 1,000 steps, but a binary search will take at most 10 steps! The Catch: The data must be sorted first.
Sorting Algorithms
• Bubble Sort: This is often considered inefficient for large sets of data. It uses nested loops to compare pairs of items, meaning as the data grows, the number of comparisons grows very quickly. It is, however, very simple to program and uses very little space (memory).
• Merge Sort: This is a "divide and conquer" algorithm. It is much more time-efficient than Bubble Sort for large lists. However, because it splits the lists into sub-lists, it uses more space (memory) to store those temporary lists.
4. Factors That Shape Algorithm Choice
When you are asked to evaluate or choose an algorithm, consider these factors:
1. Is the data already sorted?
If it is, use Binary Search. If it isn't, and you only need to search once, Linear Search is better because sorting takes extra time.
2. How much data is there?
If you only have 5 items, a Bubble Sort is fine. If you have 5 million items, you must use something more efficient like Merge Sort.
3. Are there memory limits?
On a small device (like a microwave controller) with very little RAM, you might choose an algorithm that uses less space, even if it is slightly slower.
5. Identifying and Correcting Errors
An algorithm isn't efficient if it's broken! Part of evaluating an algorithm involves trace tables. We use these to track the values of variables at every single step of the algorithm.
Quick Tip: If a trace table shows a variable looping forever or a value not changing when it should, you have found a logic error. Correcting these errors is the first step toward efficiency.
Summary: Key Takeaways
• Efficiency is about using the least amount of time (steps) and space (memory) possible.
• Binary Search is more efficient than Linear Search but requires sorted data.
• Merge Sort is more efficient than Bubble Sort for large datasets but uses more memory.
• Fitness for purpose means checking if the algorithm meets requirements and handles all test data correctly.
• Always choose your algorithm based on the size and state of the data you are using.