Mastering Algorithms: Definitions, Design Principles, and Complexity Explained

With data structures we can digitize real‑world problems, but we must process the stored data to obtain results such as searching, matching, sorting, deduplication, and optimal solutions. This article focuses on algorithm definitions and ideas.

Algorithm Definition

In simple terms, an algorithm is a step‑by‑step procedure for solving a problem.

In Java, algorithms are typically 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, due to the underlying algorithms. Sorting implementations are also important algorithmic topics.

1. Five Characteristics of Algorithms

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

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

Feasibility: All operations must be basic and realizable with a finite number of primitive actions.

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

Output: The algorithm produces a set of results that are deterministically related to the inputs.

2. Design Principles of Algorithms

Correctness : The algorithm must satisfy the specified requirements. Correctness can be evaluated at four levels: (1) syntactic correctness, (2) functional correctness for typical inputs, (3) correctness for challenging inputs, and (4) correctness for all legal inputs. The fourth level is usually the standard.

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

Robustness : The algorithm should handle illegal inputs gracefully, returning error information rather than crashing.

Efficiency and Low Storage : Execution time (time complexity) and memory usage (space complexity) should be minimized relative to the problem size.

Algorithm Time and Space Complexity

1. Measuring Algorithm Efficiency

Two main approaches are used: (1) Empirical timing with test programs, and (2) Pre‑implementation analytical estimation.

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

Thus, ignoring hardware factors, a program’s runtime depends on algorithm quality and input scale.

Example: Summing numbers from 1 to 100.

int i, sum = 0, n = 100;   // executed once<br/>for(i = 1; i <= n; i++) { // executed n+1 times<br/>    sum = sum + i;          // executed n times<br/>}

Optimized version:

int sum = 0, n = 100;<br/>sum = (1 + n) * n / 2; // executed once

The first algorithm performs roughly 2n+2 operations, while the second performs only 2 operations, illustrating the impact of algorithmic choice.

2. Asymptotic Growth of Functions

Given functions f(n) and g(n), if there exists an N such that for all n > N, f(n) > g(n), then f grows asymptotically faster than g.

Constant terms (+3, +1) become negligible as n grows.

3. Time Complexity

Time complexity T(n) describes how the number of executed statements grows with input size n, expressed as T(n) = O(f(n)). The notation O() captures the asymptotic growth rate.

Typical complexities (from fastest to slowest): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ).

4. Deriving Big‑O

Replace all additive constants with 1.

Keep only the highest‑order term.

Remove constant multipliers of the highest‑order term.

Examples:

// Constant time example<br/>int sum = 0, n = 100;<br/>printf("I love you.com
"); // repeated several times<br/>sum = (1 + n) * n / 2;

Resulting complexity: O(1).

// Linear time example<br/>int i, n = 100, sum = 0;<br/>for(i = 0; i < n; i++) {<br/>    sum = sum + i;<br/>}

Complexity: O(n).

// Quadratic time example<br/>int i, j, n = 100;<br/>for(i = 0; i < n; i++) {<br/>    for(j = 0; j < n; j++) {<br/>        printf("I love FishC.com
");<br/>    }<br/>}

Complexity: O(n²).

// Logarithmic time example<br/>int i = 1, n = 100;<br/>while(i < n) {<br/>    i = i * 2;<br/>}

Complexity: O(log n).

5. Worst‑Case vs. Average‑Case

Searching an array of n random numbers: best case O(1) (first element matches), worst case O(n) (element at the end), average case is the expected runtime over all possible positions.

6. Space Complexity

Space complexity S(n) = O(f(n)) measures the amount of memory an algorithm requires as a function of input size n.

Trade‑off example: Determining leap years by computation (low space, higher time) versus pre‑computing a 2050‑element lookup table (higher space, constant time).

Common Algorithm Design Strategies

Recursion : A function calls itself, reducing the problem size each time until a base case is reached.

Brute Force (Exhaustive Search) : Enumerate all possible solutions and test each one.

Greedy : Make the locally optimal choice at each step, hoping to reach a global optimum.

Divide and Conquer : Split the problem into independent sub‑problems, solve each recursively, then combine the results.

Dynamic Programming : Solve overlapping sub‑problems once and reuse their solutions to build up the final answer.

Iteration : Repeatedly apply a transformation to a variable until a condition is met.

Branch and Bound : Systematically explore solution space, pruning branches that cannot yield better solutions than the current best.

Backtracking : Explore possibilities depth‑first, retreating when a partial solution violates constraints.

Understanding these concepts provides a solid foundation for further study of searching, sorting, matching, and optimization algorithms.