complexity | brain

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.21 Lower Bounds for Sorting

6.21 Lower Bounds for Sorting Lower bounds describe what no algorithm can beat under a given model. For sorting, the standard model is comparison-based sorting, where the algorithm learns order only by comparing elements. In this model, any algorithm must use at least on the order of ( n \log n ) comparisons in the worst case. Problem You want to understand the inherent cost of sorting and why many...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.25 Common Failure Modes

Even when the algorithmic idea is correct, implementations fail in predictable ways. These failures are not random. They arise from mismatches between the specification, the model, and the code. Recognizing these patterns early reduces debugging time and prevents subtle errors. Problem You have an implementation that behaves incorrectly or inconsistently, and you need a systematic way to identify likely causes. Solution Check the implementation against a small set of known...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.24 Benchmarking

Benchmarking measures how an implementation behaves on real inputs and real hardware. Complexity analysis tells you how an algorithm should scale. Benchmarking tells you what the constants, memory effects, and implementation details actually do. A benchmark should answer a specific question. It should not merely produce a number. Useful questions include whether one implementation is faster than another, whether the running time grows as expected, whether memory usage fits the...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.22 Numerical Limits

Algorithms are usually described with mathematical integers and real numbers. Implementations run with finite machine values. This difference matters. An algorithm can be correct in theory and still fail in code because an integer overflows, a floating-point comparison is unstable, or a counter cannot represent the true answer. Numerical limits should be checked during design, not after debugging. The input constraints often tell you which numeric type is required. Problem...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.21 Data Representation

Data representation is the choice of concrete form used to store the objects in a problem. The same mathematical object can have many representations, and each representation makes some operations cheap while making others expensive. Choosing the representation is therefore part of algorithm design. A graph can be stored as an edge list, adjacency list, adjacency matrix, or compressed sparse structure. A set can be stored as a sorted array,...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.23 Stability and Determinism

Stability and determinism describe how predictably an algorithm behaves when there are ties, repeated values, or multiple valid answers. These properties do not always change the mathematical objective, but they often change the required output, the implementation, and the tests. An algorithm is deterministic if the same input always produces the same output. An algorithm is stable, in the common sorting sense, if equal keys keep their original relative order....

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.20 Implementation Discipline

Implementation discipline means translating an algorithm into code without changing its meaning accidentally. The pseudocode gives the structure. The implementation must preserve the same state, boundaries, invariants, and output contract. Many algorithmic bugs are not failures of the idea. They are failures of translation: an inclusive interval becomes half-open, an index update skips an element, a comparison uses < instead of <= , or an integer type overflows. Implementation discipline...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.19 Pseudocode Style

Pseudocode is a bridge between the problem statement and an implementation. It should expose the algorithmic idea without committing too early to language-specific details. Good pseudocode is precise enough to analyze, but simple enough to read as a description of the method. The purpose of pseudocode is not to look like code. Its purpose is to make control flow, data flow, invariants, and cost visible. Problem You need to describe...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.15 Dynamic Programming

Dynamic programming solves problems by storing answers to subproblems and reusing them. It is useful when a naive recursive solution repeats the same work many times. Instead of recomputing a subproblem every time it appears, the algorithm computes it once and records the result. The method depends on two properties: Optimal substructure: The answer to a larger problem can be built from answers to smaller problems. Overlapping subproblems: The same...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.18 Reductions

A reduction transforms one problem into another problem. It is a way to reuse algorithms and transfer difficulty. If problem A can be converted into problem B, and we already know how to solve B, then we can solve A by translating the input, running the solver for B, and translating the output back. Reductions are useful in two directions. For algorithm design, they let you solve a new problem...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.16 Randomization

Randomized algorithms use random choices during execution. The output or running time may depend on those choices. Randomization is useful when it simplifies design, avoids adversarial patterns, or gives good expected performance with a small amount of code. A randomized algorithm still needs a correctness contract. The contract must say whether the algorithm is always correct, probably correct, or correct in expectation. Problem You want to use randomness to make...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.17 Amortized Analysis

Amortized analysis studies the average cost of operations over a sequence, even when individual operations are sometimes expensive. It is used when a data structure has rare costly steps that are paid for by many cheap steps. The guarantee is different from average-case analysis. Amortized analysis does not require random input or a probability distribution. It gives a worst-case bound over any valid sequence of operations. Problem You have an...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.14 Divide and Conquer

Divide and conquer solves a problem by splitting it into smaller subproblems, solving those subproblems, and combining their answers. It is useful when the original problem has repeated structure and when the cost of combining subanswers is controlled. The pattern has three parts: divide: split the input into smaller pieces conquer: solve each piece recursively combine: merge the subanswers into the answer for the full input The key question is...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.13 Greedy Choices

A greedy algorithm builds a solution by making one locally best choice at a time. It does not reconsider earlier choices. This makes greedy algorithms simple and fast, but also easy to get wrong. The main difficulty is proof: you must show that each local choice can be part of some globally optimal solution. Greedy algorithms work when the problem has structure that makes local progress safe. A choice is...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.11 Testing Algorithms

Testing does not prove an algorithm correct, but it exposes mistakes in specifications, invariants, edge cases, and implementation details. A good test suite is built from the problem statement. It checks whether the implementation satisfies the input and output contract under ordinary, boundary, and adversarial conditions. Algorithm tests should not only ask, "Does this example pass?" They should ask, "What assumption would fail if this test failed?" Each test should...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.12 Brute Force Baselines

A brute force baseline is the simplest correct algorithm you can write from the problem statement. It may be too slow for the final constraints, but it is valuable because it gives you a reference answer, exposes edge cases, and clarifies what the optimized algorithm must preserve. A good baseline is intentionally direct. It should follow the definition of the problem more closely than the efficient solution does. This makes...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.10 Edge Cases

Edge cases are valid inputs that sit at the boundary of the specification. They are often small, empty, repeated, extreme, or structurally degenerate. They matter because many algorithms are designed around the typical case, while many bugs occur at the boundary. An edge case should not be treated as an exception to the problem. It is part of the problem. If the input is allowed by the specification, the algorithm...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.9 Lower Bounds

A lower bound states that every algorithm for a problem must perform at least a certain amount of work in some model of computation. It tells you what cannot be improved. Upper bounds come from algorithms. Lower bounds come from arguments about necessity. For example, if an algorithm scans an unsorted array to find the maximum value, the linear-time algorithm gives an upper bound of $O(n)$. A lower bound proves...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.8 Big O Notation

Big O notation provides a formal way to describe how a function grows. In algorithms, it is used to express upper bounds on time and space complexity. The notation suppresses constant factors and lower order terms so that the dominant growth rate is clear. Problem You have derived a function that counts operations, such as (3n^2 + 5n + 7), and you need a standard way to express its growth....

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.7 Space Complexity

Space complexity measures how much memory an algorithm uses as a function of input size. It complements time complexity and often determines whether an algorithm is feasible in practice. Memory includes both the input representation and any additional storage used during execution. The focus in algorithm design is usually on auxiliary space , which is the extra memory beyond the input itself. Problem You have an algorithm and need to...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.6 Time Complexity

Time complexity describes how the running time of an algorithm grows as the input size grows. It does not try to predict the exact number of seconds on a particular machine. Instead, it gives a portable way to compare algorithms by counting how many primitive operations they perform as a function of the input. The main size parameter is usually written as (n). For graphs, we often use two parameters:...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.5 Recursion Invariants

Recursive algorithms replace loop structure with self-reference. Instead of tracking progress through iteration, you track progress through problem size. A recursion invariant describes what each call is responsible for computing and how that responsibility relates to smaller subproblems. The core idea is simple: every recursive call must solve a strictly smaller instance of the same problem, and the combination of those solutions must produce a correct result for the original...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.2 Input and Output Models

An algorithm does not operate on an abstract idea of data. It operates on a chosen model of data. The same problem can look easy or hard depending on how the input is represented and how the output must be produced. For this reason, every serious algorithm description should state not only what the input means, but also how the input is presented to the algorithm. The input model defines...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.1 Problem Statements

An algorithm begins with a precise statement of the problem. The goal is to define the task so clearly that both correctness and complexity follow from the definition. Ambiguity at this stage propagates into proofs, implementations, and tests. A problem statement consists of four parts: input, output, constraints, and guarantees. Input specifies the structure and domain of data. You describe types, sizes, ordering, and any preconditions. For example, an input...

Programming › Algorithm Cookbook ›

Chapter 1. Foundations

This chapter defines how you think about algorithms before you write any code. It establishes a small set of rules for describing problems, reasoning about correctness, and estimating cost. Every later technique relies on these rules, so the focus here stays on precision and repeatability. An algorithm begins with a contract. You specify inputs, outputs, and constraints in a way that removes ambiguity. This includes data shape, value ranges, ordering...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.4 Loop Invariants

Loop invariants are the primary tool for reasoning about iterative algorithms. They formalize what remains true at each step of a loop and provide a bridge between local updates and global correctness. A loop invariant is not an observation after the fact. It is a design component that guides how the loop is written. Problem You need a reliable method to prove that a loop-based algorithm is correct, especially when...

Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.3 Correctness Arguments

A correctness argument explains why an algorithm returns an acceptable output for every valid input. It should be written before, or at least alongside, the implementation. Code tells you what the algorithm does. A correctness argument tells you why those steps solve the stated problem. A good correctness argument is local. It does not rely on intuition about the whole program at once. Instead, it identifies a property that remains...

Programming › Algorithm Cookbook › Chapter 3. Linked Lists and Pointers ›

3.24 Complexity Analysis

Linked list algorithms are dominated by pointer traversal and constant-time link updates. The key to correct analysis is to count how many nodes are visited and how many pointers are changed. Unlike arrays, there is no random access, so position-based operations depend on traversal length. Cost Model Use these basic costs: read next pointer: O(1) write next pointer: O(1) allocate node: O(1) free node: O(1) compare values: O(1) A loop...

Maths › 03. Logic and Foundations ›

13.5 Proof Length and Complexity

13.5 Proof Length and Complexity Proof theory can ask not only whether a formula is provable, but also how hard it is to prove. This leads to the study of proof length and proof complexity. A formal proof is a finite object, so it has a size. We may count the number of lines, the number of inference steps, the total number of symbols, or the size of the proof...

Maths › 00. General Mathematics ›

09.2 Complexity Awareness

9.2 Complexity Awareness Once we have an algorithm, a natural question follows: how efficient is it. Some methods work quickly for small inputs but become slow when the input grows. Complexity awareness is the habit of thinking about how much time or effort an algorithm needs as the problem size increases. Why efficiency matters Consider the task of finding the largest number in a list. The method from the previous...

Maths › 00. General Mathematics ›

09. Computation and Algorithms

Chapter 9. Computation and Algorithms Computation gives mathematics an operational form. It turns definitions into procedures, examples into experiments, and abstract structures into objects that can be tested, searched, and verified. Algorithms do not replace proof, but they often guide discovery, expose patterns, and make large mathematical systems usable. This chapter gives an overview of computational thinking in mathematics. It introduces algorithms as precise processes, discusses the cost of computation,...

#complexity

6.21 Lower Bounds for Sorting

1.25 Common Failure Modes

1.24 Benchmarking

1.22 Numerical Limits

1.21 Data Representation

1.23 Stability and Determinism

1.20 Implementation Discipline

1.19 Pseudocode Style

1.15 Dynamic Programming

1.18 Reductions

1.16 Randomization

1.17 Amortized Analysis

1.14 Divide and Conquer

1.13 Greedy Choices

1.11 Testing Algorithms

1.12 Brute Force Baselines

1.10 Edge Cases

1.9 Lower Bounds

1.8 Big O Notation

1.7 Space Complexity

1.6 Time Complexity

1.5 Recursion Invariants

1.2 Input and Output Models

1.1 Problem Statements

Chapter 1. Foundations

1.4 Loop Invariants

1.3 Correctness Arguments

3.24 Complexity Analysis

13.5 Proof Length and Complexity

09.2 Complexity Awareness

09. Computation and Algorithms