What Algorithms Are and How to Analyze Them: A Complete Starting Guide

What Exactly Is an Algorithm?

An Algorithm is a well-defined, finite sequence of computational steps that transforms a given input into a desired output. Every algorithm must satisfy several essential properties to be useful as a tool for solving problems.

• Finiteness: the algorithm must terminate after a finite number of steps, no matter what valid input it receives.
• Definiteness: each step must be precisely and unambiguously specified, leaving no room for interpretation.
• Input and Output: the algorithm takes zero or more inputs and produces at least one output related to those inputs.
• Effectiveness: each step must be basic enough to be carried out, in principle, by a person using pencil and paper in a finite amount of time.

A Problem is a general question to be answered, usually with parameters left unspecified, such as "sort this collection of numbers." A specific set of parameter values, such as one particular unsorted list, is called a Problem Instance. An algorithm is Correct if it produces the proper output for every possible problem instance, and it is said to Solve the computational problem.

Why Studying Algorithms Still Matters

A common misconception is that faster hardware makes algorithm efficiency less important. In reality, the gap between a well-designed and a poorly designed algorithm often grows larger, not smaller, as problem sizes increase, because different algorithms scale at fundamentally different rates.

Consider two hypothetical algorithms solving the same problem: one takes time proportional to the square of the input size, while another takes time proportional to the input size multiplied by its logarithm. For small inputs, the difference might be negligible, but as input size grows into the millions, the quadratic algorithm can become impractically slow while the other remains fast. No amount of additional hardware speed can fully compensate for choosing an algorithm with fundamentally worse scaling behavior on sufficiently large inputs.

Beyond raw efficiency, algorithms are also a technology in their own right, much like fast hardware, high-level programming languages, or compilers. Understanding algorithms allows a programmer to reason about a solution's efficiency, memory usage, and correctness independent of any particular programming language or machine.

A First Complete Example: Insertion Sort

To ground these abstract ideas, consider the Sorting Problem: given a sequence of numbers, rearrange them into non-decreasing order. One of the simplest algorithms for solving this is Insertion Sort, which works the way many people naturally sort a hand of playing cards.

How Insertion Sort Works

Insertion sort processes the input one element at a time. At each step, it takes the next unsorted element and inserts it into its correct position among the already-sorted elements that precede it.

INSERTION-SORT(A, n):
  for i = 2 to n:
      key = A[i]
      j = i - 1
      while j > 0 and A[j] > key:
          A[j + 1] = A[j]
          j = j - 1
      A[j + 1] = key

Tracing through a small example makes this concrete. Suppose the array starts as [5, 2, 4, 6, 1, 3].

Start:        [5, 2, 4, 6, 1, 3]
After i=2:    [2, 5, 4, 6, 1, 3]
After i=3:    [2, 4, 5, 6, 1, 3]
After i=4:    [2, 4, 5, 6, 1, 3]
After i=5:    [1, 2, 4, 5, 6, 3]
After i=6:    [1, 2, 3, 4, 5, 6]

At each iteration, the "key" element is compared against the sorted portion to its left and shifted backward until it lands in the correct position, growing the sorted region by one element at every step.

Proving Correctness with a Loop Invariant

To rigorously argue that insertion sort always produces a correctly sorted array, computer scientists use a technique called a Loop Invariant: a property that is true before the loop begins, remains true before each iteration, and, combined with the loop's termination condition, implies the algorithm's correctness once the loop ends. This mirrors mathematical induction.

For insertion sort, the loop invariant is: at the start of each iteration of the outer loop, the subarray A[1..i-1] consists of the original elements that were originally in that subarray, but now in sorted order.

• Initialization: before the first iteration, when i = 2, the subarray A[1..1] contains just a single element, which is trivially sorted.
• Maintenance: each iteration of the loop takes the invariant as true at its start and shows it remains true afterward, by correctly inserting A[i] into its proper sorted position within the growing sorted subarray.
• Termination: when the loop ends, i has become n + 1, so the invariant states that the subarray A[1..n], the entire array, is sorted — which is exactly what needed to be proven.

Analyzing How Long an Algorithm Takes

Beyond correctness, an algorithm's Running Time is a central concern. Running time is typically measured as a function of Input Size, the number of items being processed, and is expressed as the number of primitive operations or "steps" the algorithm performs.

Worst-Case, Best-Case, and Average-Case Analysis

Since running time can vary depending on the specific input, not just its size, three distinct notions of running time are commonly used.

• Worst-Case Running Time: the maximum running time over all inputs of a given size. This is the most commonly used measure, since it provides a guaranteed upper bound regardless of input.
• Best-Case Running Time: the minimum running time over all inputs of a given size. This is rarely useful on its own, since it does not guarantee anything about typical performance.
• Average-Case Running Time: the expected running time over some assumed distribution of inputs. This can be informative but depends heavily on the assumed distribution being realistic.

For insertion sort, the worst case occurs when the input array is sorted in reverse order, since every new element must be compared against and shifted past every previously sorted element. In this case, the number of comparisons grows proportionally to the square of the input size. The best case occurs when the array is already sorted, since the inner while loop never executes, and the algorithm runs in time proportional simply to the input size.

Why Worst-Case Analysis Is the Standard Choice

Worst-case analysis is preferred in most contexts for three practical reasons. First, it provides a guaranteed upper bound that holds regardless of the input the algorithm ultimately receives, which matters for systems that must meet reliability guarantees. Second, for many algorithms, the worst case occurs fairly often in practice, not just in rare pathological examples. Third, the average case is often nearly as bad as the worst case for many algorithms, making the extra complexity of average-case analysis not always worth the effort.

Designing Algorithms: Incremental Versus Divide-and-Conquer

Insertion sort follows an Incremental design approach: it builds the solution progressively, one element at a time, extending a partial solution until the entire problem is solved. This approach tends to produce simple, easy-to-understand algorithms, though not always the most efficient ones for large inputs.

An alternative and often more powerful design paradigm, explored in the next major topic, is Divide-and-Conquer, which breaks a problem into smaller subproblems of the same type, solves each independently (often recursively), and then combines their solutions. This approach frequently yields more efficient algorithms for large-scale problems, at the cost of somewhat greater conceptual complexity.

Why This Foundation Matters

Every algorithm studied throughout the rest of this series builds directly on the concepts introduced here: precise problem definitions, rigorous correctness arguments using techniques like loop invariants, and careful running-time analysis using worst-case reasoning. Mastering these foundational tools before moving to more advanced algorithms makes it possible to evaluate any new algorithm encountered with the same rigor applied to insertion sort in this article.