Comparing the utility of alternative algorithms for the same problem

Welcome to Comparing Algorithms!

Have you ever noticed that there is usually more than one way to solve a problem? For example, think about tidying your bedroom, getting to school, or finding a pair of matching socks. Some methods are super quick, while others take longer but are much simpler.

In Computer Science, we face the exact same challenge. For any single computing problem, programmers can design several different algorithms. But how do we decide which one to use? In this chapter, we will use logical reasoning to compare algorithms and decide which one has the highest utility (fitness for purpose) for a specific job.

Don't worry if this seems tricky at first! We will break down every concept step-by-step using clear, real-world examples.

1. What is an Algorithm and What is "Utility"?

Let's refresh two essential definitions before we start comparing:

Algorithm: An unambiguous, step-by-step sequence of instructions designed to perform a specific task or solve a computational problem.

Utility: The overall suitability, effectiveness, and practical value of an algorithm when applied to a given situation or dataset. You can think of utility as answering the question: "How fit for purpose is this algorithm for my specific task?"

The 5 Criteria for Comparing Algorithms

When computer scientists compare alternative algorithms, they evaluate five key criteria:

1. Correctness: Does the algorithm reliably produce the correct output for all valid inputs? An algorithm that is fast but gives the wrong answer has zero utility!

2. Efficiency (Time / Speed): How many steps and comparisons does the algorithm need to carry out relative to the size of the input data, represented by \(n\)?

3. Space / Memory Efficiency: How much additional working memory or storage space does the computer need while running the algorithm?

4. Simplicity and Readability: How easily can a human programmer read, understand, trace, and maintain the code?

5. Preconditions and Constraints: What state must the data be in before the algorithm can even start? For example, does the list need to be sorted into order first?

Key Takeaway: An algorithm is not simply "good" or "bad" on its own. Its utility depends entirely on the situation, the size of the data, and whether the data is already sorted.

2. Case Study 1: Searching Algorithms

A classic computational problem is finding a specific target value inside a list of items (like finding a student's name in a school register).

Algorithm A: Linear Search

How it works: A linear search starts at the very beginning of the list and checks each item one by one (sequentially) until it finds the target item or reaches the end of the list.

Real-world analogy: Imagine looking for your favourite shirt in an untidy pile of clothes on the floor. You have to pick up and look at each shirt one by one until you find it.

Precondition: None! It works on both unsorted and sorted lists.

Best-Case Utility: 1 comparison (if the target item happens to be the very first item in the list).

Worst-Case Utility: \(n\) comparisons for a list of size \(n\) (if the target is at the very end of the list, or not in the list at all).

Pros: Very simple to understand and code; works on completely unordered data.

Cons: Inefficient and slow for large datasets.

Algorithm B: Binary Search

How it works: A binary search uses a divide and conquer approach. It looks at the middle item of a list. If the middle item matches the target, the search is finished! If the target is smaller than the middle item, the algorithm discards the entire upper half of the list. If the target is larger, it discards the lower half. It repeats this process on the remaining half until the target is found.

Real-world analogy: Imagine looking for a word in a printed dictionary. You open it in the middle. If your word starts with 'T' and the middle page is 'M', you throw away the first half of the book and search only the second half.

Precondition: The data must be sorted in ascending or descending order first.

Best-Case Utility: 1 comparison (if the target is sitting exactly at the initial midpoint).

Worst-Case Utility: Number of comparisons is proportional to \(\log_2(n)\) because the search space is halved after every single check.

Pros: Extremely fast, especially on huge datasets (for example, searching through a list of 1,000,000 items takes no more than 20 comparisons!).

Cons: Cannot be used at all if the list is unsorted.

Comparing Utility: Linear Search vs. Binary Search

Which searching algorithm has higher utility?

• For small lists or frequently changing, unsorted data, Linear Search has higher utility. Why? Because sorting an unsorted list just to run a binary search takes extra time and effort that outweighs the benefit.

• For large, static, or already sorted datasets, Binary Search is far superior in speed and utility.

Key Takeaway: Linear search is flexible because it works on any list, but binary search is vastly faster for large, sorted lists.

3. Case Study 2: Sorting Algorithms

Another fundamental problem in computing is sorting: rearranging a jumbled list of items into numerical or alphabetical order.

Algorithm 1: Bubble Sort

How it works: It moves through the list comparing adjacent (side-by-side) items and swaps them if they are in the wrong order. It repeats full passes through the list until a complete pass happens with zero swaps, which confirms the list is sorted.

Utility: Simple to trace and code; very efficient if the list is already almost sorted; very slow and inefficient on large, jumbled lists.

Algorithm 2: Insertion Sort

How it works: It builds the sorted list one item at a time. It takes the next unsorted item and inserts it into its correct position relative to the items that have already been sorted.

Real-world analogy: Think of how you sort playing cards in your hand. You pick up cards one at a time and insert each card into its correct place among the cards you are already holding.

Utility: Efficient for small lists and lists that are already partially sorted; uses very little extra memory; inefficient for large, reversed lists.

Algorithm 3: Merge Sort

How it works: A divide-and-conquer algorithm that repeatedly splits a list in half until individual elements remain (sublists of length 1). It then repeatedly merges these sublists back together in sorted order until one completely sorted list remains.

Utility: Highly consistent and very fast on large datasets; however, it requires more additional working memory to store the temporary sublists while merging.

Comparing Sorting Utility: Speed vs. Memory

• Bubble Sort & Insertion Sort: Have high utility when data is small or nearly sorted, and when memory is limited (they sort items directly "in place").

• Merge Sort: Has high utility when dealing with large datasets where fast, reliable sorting speed is the top priority, provided the computer has enough working memory.

Key Takeaway: Sorting algorithms involve trade-offs. Fast divide-and-conquer algorithms like Merge Sort run quickly on large datasets but require extra memory to store split sublists.

4. Pitfalls and Common Misconceptions

Watch out for these common traps when comparing algorithms:

Pitfall 1: Believing "One algorithm is always the best"
Correction: No single algorithm is perfect for every situation. For instance, binary search is faster than linear search on large lists, but it is completely useless if the data cannot be sorted first!

Pitfall 2: Forgetting the Binary Search Precondition
Correction: Always check whether the list is ordered. You cannot perform a binary search on an unsorted list.

Pitfall 3: Thinking "Fewer lines of code = Faster algorithm"
Correction: The number of lines written in program code does not determine execution speed. A short algorithm with a loop that runs \(n\) times can take much longer than a longer, more sophisticated algorithm.

Pitfall 4: Confusing Comparisons with Swaps
Correction: In sorting algorithms like Bubble Sort, an algorithm makes a comparison every time it inspects two items, but it only makes a swap if they are in the wrong order.

Pitfall 5: Assuming Linear Search always checks every item
Correction: A linear search stops immediately as soon as it finds the target item (this is why its best-case is only 1 comparison!). It only checks all \(n\) items in the worst case.

5. Quick Summary Checklist

Before you move on, make sure you can answer these core questions:

• Can you define algorithm and utility in your own words?

• Can you name the 5 criteria used to compare algorithms (Correctness, Speed, Memory, Simplicity, Preconditions)?

• When does Linear Search have higher utility than Binary Search?

• What is the essential precondition before you can run a Binary Search?

• Why might a programmer choose Bubble Sort or Insertion Sort over Merge Sort if memory is strictly limited?