Algorithms Complexity

How to read this page: This article maps the topic from beginner to expert across six levels � Remembering, Understanding, Applying, Analyzing, Evaluating, and Creating. Scan the headings to see the full scope, then read from wherever your knowledge starts to feel uncertain. Learn more about how BloomWiki works ?

Algorithms and Complexity are the mathematical foundations of computer science. An algorithm is a precise, step-by-step procedure for solving a problem or performing a task. Complexity theory is the study of how much "effort"—in terms of time (CPU cycles) and space (RAM)—an algorithm requires to complete as the size of the input grows. Understanding these concepts allows computer scientists to write efficient code, predict how systems will scale, and identify which problems are fundamentally "hard" or even impossible for computers to solve.

Remembering

• Algorithm — A finite set of instructions to solve a specific problem.
• Computational Complexity — A measure of the resources (time and space) needed to run an algorithm.
• Big O Notation — A mathematical notation that describes the limiting behavior of a function (the "worst-case" scenario).
• Time Complexity — How the execution time of an algorithm grows with the input size (n).
• Space Complexity — How the memory usage of an algorithm grows with the input size (n).
• P (Complexity Class) — Problems that can be solved in "polynomial time" (efficiently).
• NP (Complexity Class) — Problems where a solution can be verified in polynomial time, but not necessarily solved.
• NP-Complete — The "hardest" problems in NP; if one is solved efficiently, they all are.
• Recursion — A method where a function calls itself to solve smaller instances of the same problem.
• Greedy Algorithm — An algorithm that makes the locally optimal choice at each step.
• Dynamic Programming — An optimization technique that solves complex problems by breaking them into overlapping subproblems.
• Divided and Conquer — An algorithm design pattern that breaks a problem into two or more sub-problems of the same or related type.
• Heuristic — A technique designed for solving a problem more quickly when classic methods are too slow.
• Sorting — The process of arranging data in a specific order (e.g., QuickSort, MergeSort).
• Searching — The process of finding a specific item in a dataset (e.g., Binary Search).

Understanding

In computer science, we don't care how fast an algorithm is for 10 items; we care how fast it is for 10 billion.

Big O Notation: This is the "speed limit" of an algorithm.

• O(1) (Constant): Takes the same time regardless of size (e.g., looking up an array index).
• O(log n) (Logarithmic): Extremely fast; doubling the input only adds one step (e.g., Binary Search).
• O(n) (Linear): Time grows directly with size (e.g., searching an unsorted list).
• O(n²) (Quadratic): Time grows with the square of size; becomes very slow quickly (e.g., Bubble Sort).
• O(2ⁿ) (Exponential): Becomes impossible for even small inputs (e.g., solving the Traveling Salesperson Problem exactly).

The P vs. NP Question: The most famous unsolved problem in computer science. It asks: "If a solution to a problem can be verified quickly, can it also be solved quickly?" Most scientists believe P ≠ NP, meaning there are some problems that are fundamentally "hard" for any computer.

Optimization: Complexity theory tells us when to stop looking for a "perfect" answer. For NP-hard problems, we often use Heuristics or Approximation Algorithms that give a "good enough" answer in a reasonable amount of time.

Applying

Comparing Linear Search vs. Binary Search: <syntaxhighlight lang="python"> def linear_search(arr, target):

   """O(n) complexity: checks every item."""
   steps = 0
   for item in arr:
       steps += 1
       if item == target: return steps
   return steps

def binary_search(arr, target):

   """O(log n) complexity: halves the search space each step."""
   low = 0
   high = len(arr) - 1
   steps = 0
   while low <= high:
       steps += 1
       mid = (low + high) // 2
       if arr[mid] == target: return steps
       elif arr[mid] < target: low = mid + 1
       else: high = mid - 1
   return steps

1. Test with 1 million items

data = list(range(1000000)) target = 999999

print(f"Linear Search steps: {linear_search(data, target)}") # ~1,000,000 print(f"Binary Search steps: {binary_search(data, target)}") # ~20

1. Binary search finds 1 item in a million in just 20 guesses!

</syntaxhighlight>

Real-World Algorithms

Google Search → PageRank (an algorithm for ranking web pages).

GPS/Google Maps → Dijkstra's Algorithm (finding the shortest path).

Cryptography → RSA (based on the complexity of factoring large prime numbers).

Compression → Huffman Coding (making files smaller without losing info).

Analyzing

Common Sorting Algorithms

Algorithm	Best Case	Worst Case	Stability
QuickSort	O(n log n)	O(n²)	Unstable
MergeSort	O(n log n)	O(n log n)	Stable
Bubble Sort	O(n)	O(n²)	Stable
HeapSort	O(n log n)	O(n log n)	Unstable

The Space-Time Tradeoff: Often, we can make an algorithm faster (lower time complexity) by using more memory (higher space complexity). A common example is Caching or Memoization, where we store the results of expensive calculations so we don't have to do them again. Analyzing this tradeoff is a core task for software architects.

Evaluating

Evaluating an algorithm: (1) Correctness: Does it always produce the right answer for all possible inputs? (2) Efficiency: Does it meet the Big O requirements of the system? (3) Robustness: How does it handle "edge cases" (e.g., empty lists or massive inputs)? (4) Simplicity: Is the code maintainable, or is it so complex that it will be buggy?

Creating

Future Frontiers: (1) Quantum Algorithms: Developing algorithms like Shor's (for factoring) and Grover's (for searching) that run exponentially faster on quantum computers. (2) Distributed Algorithms: Designing algorithms that can run across thousands of machines simultaneously (Cloud computing). (3) Differential Privacy: Algorithms that can extract useful patterns from data while mathematically proving that individual privacy is protected. (4) Self-Optimizing Algorithms: Using machine learning to "tune" the parameters of an algorithm automatically based on the data it sees.