ASKiIMAN™ REALM 08 / COMPUTING
--:-- · -- --- ----
O(n log n)

The Algorithm Engine

Searching, Sorting, Complexity & Efficient Computation

Central Doctrine

An algorithm can solve a problem correctly and still be entirely impractical if it requires too much time or memory. This realm studies the mathematics of computational efficiency. We decode the major algorithmic techniques used to search, sort, traverse, and optimize data, mapping the strict limits of what a computer can achieve within the constraints of time and space.

DATA → ALGORITHM → SORT / SEARCH → TIME COMPLEXITY → SPACE COMPLEXITY → TRADE-OFFS → OPTIMIZATION

The Internal Chambers

Ontology of Computational Efficiency

CHAMBER 01

Algorithmic Efficiency

  • Running time and Memory usage
  • Scalability relative to input size
  • The practical cost of computation
  • Balancing computational trade-offs
CHAMBER 02

Asymptotic Analysis & Big-O

  • Measuring growth rate as input (n) scales
  • Ignoring constants and lower-order terms
  • Big-O: Upper bound worst-case
  • Big-Ω & Big-Θ: Lower and tight bounds
CHAMBER 03

The Complexity Ladder

O(1) < O(log n)
O(n) < O(n log n)
O(n²) < O(2ⁿ)
  • O(1) & O(log n): Constant/Logarithmic (Extremely fast)
  • O(n) & O(n log n): Linear/Linearithmic (Scalable)
  • O(n²): Quadratic (Nested loops)
  • O(2ⁿ) & O(n!): Exponential (Combinatorial explosion)
CHAMBER 04

Space & Case Analysis

  • Space Complexity: Auxiliary memory and recursion stack
  • In-place algorithms (O(1) space)
  • Best, Average, and Worst-case input scenarios
  • Why worst-case guarantees matter for systems
CHAMBER 05

Searching Algorithms

  • Linear Search: O(n) sequential scan. Works on unsorted data.
  • Binary Search: O(log n) repeated halving. Requires sorted data.
  • Search everything vs. Eliminate half each step
CHAMBER 06

Sorting & Stability

5a
5b
↓ STABLE ↓
5a
5b
  • Why sorting is foundational to computation
  • Stable sorting: Preserves original relative order of equal keys
  • In-place sorting: Operates without auxiliary memory arrays
CHAMBER 07

O(n²) Sorts

  • Bubble Sort: Adjacent swapping
  • Selection Sort: Minimum extraction
  • Insertion Sort: Efficient for small or nearly sorted datasets
  • Simple to implement, poor scaling
CHAMBER 08

O(n log n) Sorts

  • Merge Sort: Divide & Conquer, stable, requires O(n) space
  • Quick Sort: Partitioning via Pivot, fast average, O(n²) worst-case
  • Heap Sort: In-place, unstable, relies on Max-Heap
CHAMBER 09

O(n) Linear Sorts

  • Bypassing the Ω(n log n) comparison barrier
  • Counting Sort: Frequency arrays for small integer ranges
  • Radix Sort: Digit-by-digit bucket processing
  • Trades space complexity for time efficiency
CHAMBER 10

Divide & Conquer

  • Divide: Break into independent subproblems
  • Conquer: Solve recursively
  • Combine: Merge results into final answer
  • Foundation of Merge Sort and Binary Search
CHAMBER 11

Greedy Algorithms

10
5
1
  • Making the optimal local choice at every step
  • Does not look ahead or reconsider past choices
  • Works if problem has "Optimal Substructure" and "Greedy Choice Property"
  • Fast, but can fail to find the global optimum
CHAMBER 12

Dynamic Programming

0
1
1
2
3
5
8
13
  • Overlapping subproblems & Optimal substructure
  • Memoization: Top-down caching of recursion
  • Tabulation: Bottom-up iterative table building
  • Trading memory space to save exponential time
CHAMBER 13

Backtracking & Brute Force

  • Brute Force: Exhaustively searching all O(2ⁿ) or O(n!) possibilities
  • Backtracking: Building a candidate, abandoning it (pruning) if it violates constraints
  • Used for Permutations, Combinations, N-Queens
CHAMBER 14

Two Pointers & Windows

  • Two Pointers: Moving left/right indices inward on sorted arrays
  • Sliding Window: Maintaining a fixed or variable subset of contiguous elements
  • Optimizes O(n²) nested loops down to O(n)
CHAMBER 15

Prefix Sums & Hashing

O(1)
  • Prefix Sums: Precomputing cumulative arrays for O(1) range queries
  • Hash Maps: Trading O(n) space for O(1) lookup time
  • Frequency counting and duplicate detection optimization
CHAMBER 16

Tree & Graph Traversal

  • BFS: Queue-based. Explores layer-by-layer. Finds unweighted shortest path.
  • DFS: Stack/Recursion-based. Explores deeply. Good for cycle detection and backtracking.
  • Complexity: O(V + E)
CHAMBER 17

Shortest Path & MST

  • Dijkstra's: Weighted shortest path
  • Minimum Spanning Tree (MST): Connecting all nodes with minimum total edge weight
  • Kruskal's and Prim's greedy strategies
CHAMBER 18

Topological Sorting

A
→
B
→
C
  • Ordering nodes based on directed dependencies
  • Only applies to Directed Acyclic Graphs (DAGs)
  • Kahn's Algorithm and DFS-based approaches
  • Used for build systems and task scheduling
CHAMBER 19

Limits & Proofs

Ω(n log n)
  • Proving correctness via Loop Invariants and Induction
  • Computational lower bounds
  • Why comparison sorting cannot be faster than Ω(n log n)
  • Information-theoretic limits
CHAMBER 20

Heuristics & Approximation

  • Heuristics: Rules of thumb for "good enough" answers
  • Approximation: Guaranteed near-optimal solutions
  • Randomized Algorithms: Using chance to improve expected practical running time (e.g., Randomized Quicksort)
CHAMBER 21

Streaming & Parallel

01011010110010101
  • Online vs Offline: Making decisions as data arrives
  • Streaming: Processing massive data in one pass with limited memory
  • Parallel Algorithms: Distributing work to overcome single-thread limits
CHAMBER 22

Complexity Table

Linear SearchO(n)
Binary SearchO(log n)
Bubble/Insert SortO(n²)
Merge/Heap SortO(n log n)
Hash Lookup (Avg)O(1)
BFS / DFSO(V+E)
FINAL CHAMBER

The Bridge to the OS

REALM 08 taught mathematical optimization:
DATA → ALGORITHM → COMPLEXITY
↓
But algorithms need an environment.
How do we SCHEDULE and ALLOCATE?
  • We have optimized the logic.
  • Now we need a master program to manage the hardware.
  • Next, we explore the software that runs the machine itself.
Proceed to REALM 09 → THE OPERATING MACHINE