Fundamental Concepts in Algorithm Design and Complexity Analysis
Algorithm Analysis vs. Algorithm Design Difficulty
When performing algorithm analysis, an algorithm already exists. The task involves applying established rules of analysis, such as:
- Rules for sequence structure.
- Rules for selection structure.
- Rules for repetition/iteration structure.
- Recurrence rules for recursion.
While some algorithms involve complex nested structures, the analyst always has a “specimen” to study and analyze. This is not the case when one has to design an algorithm.
Algorithm design is inherently more challenging. The designer may be fortunate enough to be assigned a problem for which an algorithm already exists, requiring only minor adjustments (e.g., tailoring the interface, adjusting input/output presentation, or modifying problem-size-related parameters).
However, at times, the problem is novel, and an algorithm does not yet exist. One then has to devise a solution using known algorithmic approaches, such as an incremental approach or a recursive approach.
The task becomes extra difficult when one has to demonstrate the algorithm’s correctness. The definition of algorithm correctness requires that it produce the expected output for all possible inputs. For truly critical problems (e.g., software for medical devices or managing subway trains), a formal proof of correctness is required, which is often an intractable exercise.
For most instances, testing is the primary means used to show program correctness. But testing can only occur after the algorithm has been designed and implemented. Designing and proving correctness is almost always much harder than analyzing an existing algorithm.
Graphs: Definition and Importance in Algorithms
Graphs are a means of representing relationships between objects in a graphical way. They are perhaps the second simplest mathematical structure—if a set is the simplest, a graph, defined by two sets (a vertex set and an edge set), must be close behind.
For simple graphs, the edge set is a subset of the Cartesian product of the vertex set with itself. Thus, a simple graph is essentially made of “one-and-a-half sets.”
As basic structures, graphs can represent all sorts of objects and their relationships. Even programs can be represented using graphs, where vertices are the statements in the program and edges represent the flow of logic. This is used prominently in software engineering theory.
In algorithm design, graph-theoretic approaches help solve various problems, including:
- Shortest path problems.
- Maximum flow problems.
- Search problems.
In algorithm analysis, graphs (in particular, trees) have been used prominently in proving lower bound results—for example, the $\Omega(n \lg n)$ lower bound on binary-comparison sorting.
NP-Complete Problems and the P vs. NP Question
Formally speaking, an NP-complete problem is a problem that is in the complexity class NP, and to which any other problem in NP can be transformed (reduced) in polynomial time. That is, we can solve any problem in NP by transforming it to the NP-complete problem, solving this transformed version, and then deriving the solution to the original from its solution.
The Compelling Reason for P $\neq$ NP
The statement that “perhaps the most compelling reason why theoretical computer scientists believe that P $\neq$ NP comes from the existence of the class of NP-complete problems” is highly compelling.
There are literally thousands of known NP-complete problems. Over the span of around 40 years, the best algorithm designers and complexity theorists have not devised a polynomial-time solution to any of them. With so many “targets” for such an effort and so many minds working at a deterministic polynomial solution, why has not one of them been polynomially solved?
If even just one of the thousands were polynomially solved, then all problems in NP could then be solved in deterministic polynomial time (i.e., NP collapses into P, meaning P=NP). The lack of success strongly suggests that the opposite is true: P is properly contained in NP, and hence P $\neq$ NP.
Heap vs. Binary Search Tree: Differences and Similarities
Both heaps and Binary Search Trees (BSTs) are binary tree structures, and both contain values in their nodes. However, they enforce fundamentally different ordering properties:
- Max Heap Property: For a max heap, the value stored at a node is greater than or equal to the values stored in both of its child nodes.
- Binary Search Tree Property: The left subtree contains values less than the value stored at the node, while the right subtree contains values greater than it.
This condition must hold true at all levels of the respective tree structures.
Can a Binary Tree Be Both?
A binary tree can only satisfy both the Max Heap property and the BST property simultaneously under very restricted circumstances, primarily when the right subtree is absent.
Examples of trees that satisfy both properties:
- An empty tree.
- A tree with just one node.
- A tree that consists of only a root and its left child (if one honors the additional requirement that a heap must be a complete binary tree).
If the additional requirement that a heap must be a complete binary tree is not honored, a tree consisting of nodes that only have left children could also satisfy both properties.
Why Merge Sort is Not an In-Place Algorithm
An in-place sorting algorithm requires no more than $O(1)$ additional memory space beyond the input array to carry out its sorting work. This is the case with algorithms like Insertion Sort and Heap Sort.
However, Merge Sort is not in-place because it requires significant auxiliary space. Merge Sort makes use of an auxiliary array that is of size $n$ (the same size as the input array) to receive the result of the merge step after the two recursive calls on the halves of the input array have returned the two halves already sorted within themselves.
Hence, Merge Sort uses $\Theta(n)$ additional space, which disqualifies it from being an in-place sorting algorithm.
The Role of Merge Sort
Merge Sort has a crucial role in sorting huge collections of values because it can perform the merge step with “page-sized” portions of results from lower-level recursive calls and store partial results in the same manner. This makes Merge Sort useful when the size of the set to be sorted cannot fit entirely in the computer’s RAM (external sorting).
Sorting Complexity: $\Omega(n \lg n)$ vs. $O(n)$
The key distinction between these two classes of sorting algorithms lies in whether their sorting logic relies on binary comparisons of the items being sorted.
Comparison-Based Sorting ($\Omega(n \lg n)$)
Sorting algorithms that base their logic on binary comparisons cannot escape the $\Omega(n \lg n)$ lower bound on the best-case complexity of the algorithm. This is demonstrated using decision trees.
Examples of comparison-based sorting algorithms:
- Insertion Sort
- Bubble Sort
- Merge Sort
- Heap Sort
Their worst-case complexity is typically $O(n \lg n)$.
Non-Comparison-Based Sorting ($O(n)$)
Algorithms that do not base their sorting logic on binary comparisons can achieve the absolute lower bound on the worst-case complexity of any sorting algorithm: $\Omega(n)$. This result is due to the fact that any sorting algorithm must examine all the values to be sorted.
By “changing the rules,” one can “beat” the comparison-based lower bound. Examples include:
- Counting Sort: Achieves $O(n)$ worst-case complexity (deterministic).
- Radix Sort: Achieves $O(n)$ worst-case complexity (deterministic).
- Bucket Sort: Achieves $O(n)$ expected complexity.
If an algorithm claims to sort in $O(n)$ worst-case time, it must either not be doing the sorting based on binary comparisons, or its analysis must be flawed. A third possibility is that it uses a different model of computation (e.g., quantum computing) where the unit cost differs from the standard model.
Time Complexity as the Primary Algorithm Criterion
Time complexity is the primary criterion used when comparing alternative algorithms to solve a problem because time is irrecoverable. Space (memory) can be recycled or expanded by adding more memory to the computing device. On the other hand, time cannot be expanded per se—although one can virtually do this by using a faster computer, an enhancement that is probably more costly than just increasing available memory.
This discussion presupposes that the alternative solutions are both correct; otherwise, they would be useless.
Considering Development Time
We typically do not use criteria like development time spent by software designers because there is more variability in them. For example, some programmers are simply more efficient at producing code than others, so development time might not be an accurate gauge of which alternative solution should be adopted.
The trade-off between development time and running time is complex:
- A more efficient solution might take forever to program, negating any time savings in running time if the program is run infrequently.
- A less efficient solution might be implemented quickly, but if the resulting program has to be run many, many times over several years, a more efficient solution might be preferable since the total time savings would still be significant.
External factors, such as labor costs, also play a role. If labor is cheap (as in some countries), it may be advantageous to have a more efficient algorithm implemented even if it took a long time to do this. Conversely, if labor costs are steep, a quick and dirty solution that may not be the most efficient may be preferable, especially if the resulting program is going to be run only a few times.
Finally, the relative difficulty of actually proving an algorithm is correct in a mathematically rigorous way might sometimes prevent correctness (in the total sense) from being the primary criterion.