Computer Science (9645) | Classification of algorithms

Welcome to the Classification of Algorithms!

Hey there! This chapter might sound very theoretical, but it’s actually one of the most practical parts of Computer Science. Why? Because you’re learning how to judge a computer program before you even run it!

We’re going to explore how we measure the efficiency of algorithms—specifically, how their performance holds up when the amount of data they handle gets *huge*. Think of it as predicting whether your app will crash when millions of users try to log in at once. This ability to classify algorithms is essential for building fast, reliable software.

---

1. Comparing Algorithms: Efficiency Matters (3.13.5.1)

When we compare two algorithms that solve the same problem (like searching for an item), we don't just ask which one is fastest on a small amount of data. We ask: "How does it cope when the size of the problem increases?"

1.1 The Size of the Problem (N)

The core concept when analyzing an algorithm is the size of the problem, often represented by the variable \(n\).

Example: If you are searching through a list, \(n\) is the number of items in that list. If you are sorting an array, \(n\) is the number of elements to be sorted.

1.2 Dimensions of Efficiency

Algorithms are generally compared in two main ways:

Time-Wise Efficiency (Time Complexity)

This refers to the amount of time an algorithm takes to complete its task. Crucially, we measure this by counting the number of steps or operations performed, not the actual seconds on a clock (because that depends on the computer’s speed).

• We look at how the number of operations grows relative to \(n\).

Space-Wise Efficiency (Space Complexity)

This refers to the amount of memory (storage or resources) an algorithm needs to run.

• A very efficient algorithm minimizes the amount of extra memory it needs to complete its task.

Key Takeaway: An efficient algorithm is one that runs quickly (low time complexity) and uses minimal extra memory (low space complexity), especially as the input size \(n\) grows.

---

2. Order of Complexity and Big O Notation (3.13.5.2)

Big O notation is the language we use to express how quickly an algorithm's performance scales up as the problem size (\(n\)) increases. It focuses on the growth rate, ignoring small details and constants.

Don't worry if this looks mathematical—we are focusing on understanding the general trend!

2.1 Understanding the Growth Rates

Here are the fundamental Big O classifications, ordered from fastest (best) to slowest (worst):

1. Constant Time: \(O(1)\)

• The running time is constant, regardless of the size of the input \(n\).

• Analogy: Checking the colour of the first car in a queue. It doesn't matter if the queue has 10 cars or 10,000; the time taken is always the same.

• Example: Accessing an element in an array using its index.

2. Logarithmic Time: \(O(\log n)\)

• The running time grows very slowly. This happens when the algorithm repeatedly halves the size of the problem space.

• Analogy: Looking up a word in a huge dictionary. You don't start at the first page; you open it roughly in the middle, eliminating half the book instantly.

• Example: Binary Search.

3. Linear Time: \(O(n)\)

• The running time grows directly and proportionally with the input size \(n\).

• Analogy: Searching for a misplaced book on a shelf. You must check every single book until you find it.

• Example: Linear Search, iterating through a list once.

4. Polynomial Time: \(O(n^a)\)

• The running time grows quickly, often represented as \(O(n^2)\) (quadratic time).

• This usually happens when an algorithm uses nested loops, where for every item \(n\), you perform another operation on all \(n\) items.

• Example: Bubble Sort.

5. Exponential Time: \(O(a^n)\)

• The running time grows incredibly fast—unfeasibly fast for even moderately large values of \(n\).

• Algorithms in this class are usually only practical for very small inputs.

2.2 Best-Case vs. Worst-Case Complexity

The complexity of an algorithm can change dramatically depending on the input data. We define two main scenarios:

• Worst-Case Complexity: This is the maximum time an algorithm will take for any input of size \(n\). This is usually the most important measure because it gives you a guarantee.
• Best-Case Complexity: This is the minimum time an algorithm will take. This often occurs if the data is already perfectly arranged (e.g., finding the item you are searching for is the first element).

Example: Bubble Sort Efficiency

Bubble Sort compares adjacent elements and swaps them. The number of comparisons depends heavily on how sorted the list is:

• Worst-Case: The list is in reverse order. It requires many comparisons and swaps. Time complexity is \(O(n^2)\).
• Best-Case: The list is already sorted. An efficient version of Bubble Sort checks if any swaps were made in a pass and stops if none were made. Time complexity is \(O(n)\).

2.3 Complexities of Standard Algorithms (Required Knowledge)

You must know the best-case and worst-case time complexities for these key algorithms:

Algorithm	Worst-Case Time Complexity	Best-Case Time Complexity
Linear Search	\(O(n)\) (Item is last or not present)	\(O(1)\) (Item is the first element)
Binary Search	\(O(\log n)\)	\(O(1)\) (Item is the middle element)
Bubble Sort	\(O(n^2)\)	\(O(n)\) (List is already sorted)
Merge Sort	\(O(n\ \log n)\)	\(O(n\ \log n)\)
Dijkstra's Shortest Path	\(O(n^2)\) (or better, depending on implementation)	\(O(n^2)\)
Searching a Binary Search Tree (BST)	\(O(n)\) (If the tree is badly structured/linear)	\(O(\log n)\) (If the tree is balanced)

Key Takeaway: Big O notation classifies algorithms based on their growth rate. Logarithmic, Linear, and efficient Polynomial algorithms are generally considered good. Sorting algorithms like Merge Sort (always \(O(n\ \log n)\)) are much more efficient than Bubble Sort (worst-case \(O(n^2)\)).

---

3. Classification of Algorithmic Problems (3.13.5.3)

Based on their time complexity, we can classify the problems themselves.

3.1 Tractable Problems

A problem is tractable if there exists an algorithm to solve it in polynomial time or less.

• This includes \(O(1)\), \(O(\log n)\), \(O(n)\), and \(O(n^a)\) where \(a\) is a constant (like \(O(n^2)\) or \(O(n^3)\)).
• Tractable problems are considered realistically solvable by a computer, even for large inputs.

3.2 Intractable Problems

A problem is intractable if there is no known algorithm to solve it in polynomial time.

• These problems usually require exponential time, like \(O(2^n)\).
• While technically solvable (computable), they are effectively unsolvable for large values of \(n\) because the time taken becomes astronomically long (e.g., searching every possible combination in a massive dataset).

3.3 Dealing with Intractable Problems: Heuristics

Since we can’t find a perfect solution for intractable problems in a reasonable time, we often use heuristic methods.

A heuristic is a set of rules or knowledge about the problem domain that helps find a solution that is "good enough," even if it’s not the mathematically perfect solution.

A heuristic method might:

• Find an approximate but non-optimal solution to a problem (e.g., finding a fast route, but maybe not the absolutely fastest one).
• Change some of the problem constraints to make it solvable faster.

Example: The Travelling Salesperson Problem (finding the shortest route visiting many cities) is intractable. A heuristic approach might involve using a greedy method—always choosing the nearest unvisited city next—which provides a good route, but might not be the absolute shortest.

Key Takeaway: Tractable problems are solvable efficiently (in polynomial time). Intractable problems require too much time (usually exponential time), so we often resort to heuristics to find quick, approximate solutions.

---

4. Computable and Non-Computable Problems (3.13.5.4)

Now we move beyond simply being slow (intractable) to problems that computers cannot solve at all.

4.1 The Halting Problem

The Halting Problem is the most famous example of a problem that cannot be solved algorithmically.

Definition: The Halting Problem asks if it is possible to create a general algorithm that, given a description of any arbitrary program and its input, can determine whether that program will eventually stop (halt) or continue to run forever in an infinite loop, without executing the program.

The crucial finding of Alan Turing was that this problem is unsolvable. No such general algorithm can exist.

4.2 Significance for Computation

The Halting Problem demonstrates the theoretical limits of computation.

• It proves that there are some problems that cannot be solved by a computer, regardless of how fast the computer is or how long you wait.
• It defines what is computable (solvable by an algorithm, like sorting) and what is non-computable (the Halting Problem).

Did you know? The theory that proves the Halting Problem is unsolvable relies on a method called 'proof by contradiction,' showing that if such a program existed, it would lead to a logical impossibility.

Key Takeaway: The Halting Problem is non-computable. It proves that computers cannot solve every problem algorithmically, setting a fundamental limit on what software can achieve.

---

Chapter Summary: Classification Review

Understanding these classifications helps you choose the right tool for the job. You need an algorithm that performs well under pressure (low Big O complexity).

• Efficiency: Measured in time (steps) and space (memory) relative to input size \(n\).
• Big O: Describes the growth rate of efficiency (\(O(1)\) is best, \(O(n^a)\) is okay, \(O(a^n)\) is usually terrible).
• Tractable: Solvable in polynomial time or less (e.g., Merge Sort).
• Intractable: Solvable, but requires exponential time, making it impractical for large inputs (often requires heuristics).
• Non-Computable: Cannot be solved by any algorithm at all (e.g., the Halting Problem).

Keep tracing those simple algorithms to understand how their operations relate to \(n\)!