Mastering Algorithms: Definitions, Design Principles, and Complexity

With data structures we can digitize real‑world problems, but we must process stored data to obtain results such as search, match, sort, deduplicate, or optimal solutions. This article focuses on algorithm definitions and ideas.

What is an algorithm?

An algorithm is simply a step‑by‑step procedure for solving a problem.

In Java, algorithms are usually implemented as class methods. For example, linked lists have fast insertion/deletion but slow search, while balanced binary trees provide fast operations for all three; sorting algorithms are also algorithmic implementations.

1. Five characteristics of algorithms

Finiteness: For any valid input, the algorithm terminates after a finite number of steps.

Determinism: Each step is precisely defined, leading to a single execution path.

Feasibility: Every operation must be basic enough to be performed a finite number of times using already implemented primitives.

Input: The algorithm processes a set of input values, which may be supplied during execution or be implicit.

Output: The algorithm produces a set of results that are uniquely determined by the inputs.

2. Design principles

Correctness : The algorithm must satisfy the specified requirements. Correctness can be evaluated at four levels, from syntactic correctness to handling all legal inputs.

Readability : Algorithms should be easy for humans to understand and maintain.

Robustness : The algorithm should handle illegal inputs gracefully, returning error information instead of crashing.

Efficiency and low storage demand : Efficiency refers to execution time, while storage demand refers to the maximum memory used; both depend on problem size.

3. Time and space complexity

Measuring algorithm efficiency

Two approaches: post‑execution timing with test programs, and pre‑analysis using theoretical estimation.

Factors influencing runtime include algorithmic strategy, compiled code quality, input size, and hardware speed.

Asymptotic growth

Big‑O notation expresses how the running time T(n) grows with input size n, ignoring constant terms and lower‑order terms.

Examples of complexity analysis

int i, sum = 0, n = 100;
for(i = 1; i <= n; i++) {
    sum = sum + i;
}

Versus

int sum = 0, n = 100;
sum = (1 + n) * n / 2;

The first loop runs O(n) steps, the second runs O(1).

Common complexity classes

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ).

Worst‑case and average‑case

Worst‑case runtime guarantees the maximum time an algorithm may take; average runtime is the expected time over all inputs.

4. Space complexity

Space complexity S(n) = O(f(n)) measures the amount of memory an algorithm requires, often traded off against time.

5. Common algorithmic strategies

Recursion

Exhaustive (brute‑force) search

Greedy algorithms

Divide and conquer

Dynamic programming

Iterative methods

Branch and bound

Backtracking

Understanding these concepts provides a solid foundation for studying specific algorithms such as searching, sorting, matching, and optimization.