What you will learn

• Big-O notation
• Time complexity
• Space complexity
• P
• NP
• NP-hard
• NP-complete
• Reductions
• Turing machines
• Non-determinism
• Cook–Levin theorem
• SAT
• 3-SAT
• CLIQUE
• Vertex cover
• PSPACE
• TQBF
• Approximation algorithms
• Interactive proofs

Course content (15 lessons)

1. Course Introduction: The Science of Hard Problems — Welcome to Complexity Theory Algorithms courses ask: how fast can we solve this problem? Complexity theory asks the deeper question: how fast can this problem possibly be solved —…
2. Unit 1: Time & Space Complexity and Big-O Notation — 1.1 What exactly are we measuring? For an algorithm A and input of size n (bits, array length, number of vertices — state your convention!): Time complexity T(n): the maximum…
3. Unit 1: The Complexity Classes — P, NP, NP-Hard, NP-Complete — 2.1 Class P — solvable fast P = the class of decision problems (languages) decidable by a deterministic algorithm in polynomial time , i.e. time O(nᵏ) for some constant k.…
4. Unit 1: Polynomial-Time Reductions — 3.1 The idea: solving A by translating it into B A polynomial-time (many-one/Karp) reduction from A to B, written A ≤ₚ B , is a function f computable in polynomial time such that…
5. Unit 2: Turing Machines & Their Variants — 1.1 Why we need a formal machine Statements like "no polynomial algorithm exists" quantify over all possible algorithms — impossible unless "algorithm" has a mathematical…
6. Unit 2: Non-deterministic Computation — 2.1 The non-deterministic Turing machine (NTM) One change to the model: the transition function returns a set of possible moves — δ : Q × Γ → 𝒫 (Q × Γ × {L, R}) At each step the…
7. Unit 2: Circuit Complexity & Random Access Machines — 3.1 Boolean circuits — hardware as a complexity model A Boolean circuit with n inputs is a directed acyclic graph whose internal nodes ( gates ) are labelled AND (∧), OR (∨), NOT…
8. Unit 2: Complexity of Concrete Algorithms — Sorting, Searching, Graphs — 4.1 Searching Algorithm Requirement Time Space :--- :--- :--- :--- Linear search none O(n) O(1) Binary search sorted array O(log n) O(1) Hash table lookup hash function O(1)…
9. Unit 3: The Cook–Levin Theorem — 1.1 The statement Cook–Levin Theorem (1971/1973). SAT — the satisfiability problem for Boolean formulas in CNF — is NP-complete . This is the keystone: the first problem proved…
10. Unit 3: The Classic NP-Complete Problems — SAT, 3-SAT, CLIQUE — 2.1 SAT — the root problem SAT: given a CNF formula φ — an AND of clauses , each an OR of literals (a variable or its negation) — does an assignment make φ true? NP-complete by…
11. Unit 3: Techniques for Proving NP-Completeness — 3.1 The standard recipe (write it at the top of every answer) To prove problem B NP-complete: 1. B ∈ NP. Name the certificate; argue the verifier is polynomial. (One sentence —…
12. Unit 4: P vs NP — The Problem and the Consequences of P = NP — 1.1 The statement P vs NP: Is P = NP? Equivalently: can every problem whose solutions are quickly verifiable also be quickly solved ? Equivalently (via Cook–Levin): does SAT have…
13. Unit 4: PSPACE & Complexity Beyond Polynomial Time — 2.1 PSPACE — polynomial memory, unlimited patience PSPACE = problems decidable using polynomial space (memory), with no time restriction. NPSPACE = the non-deterministic version —…
14. Unit 4: Living with Hardness — Approximation Algorithms & Interactive Proofs — 3.1 NP-hard in practice: the coping strategies P ≠ NP (presumably) forbids only exact + worst-case-fast + general . Drop any one: Drop Strategy Example :--- :--- :--- exactness…
15. Quick Revision & Exam Preparation — The 20 definitions you must write precisely 1. f = O(g): ∃ c, n₀ 0 : f(n) ≤ c·g(n) ∀ n ≥ n₀ (Ω: ≥; Θ: both). 2. Time/space complexity: worst-case steps / cells used as a function…

Course Introduction: The Science of Hard Problems

Welcome to Complexity Theory

Algorithms courses ask: how fast can we solve this problem? Complexity theory asks the deeper question: how fast can this problem possibly be solved — by any algorithm, ever? It is the study of the inherent difficulty of computational problems, and it contains the most famous open question in computer science: does P equal NP?

The journey of this course

How this course is organised

Why this subject matters to you

1. It tells you when to stop looking for a fast algorithm. Recognising that a scheduling/routing/packing problem is NP-complete saves weeks of doomed optimisation and points you to approximations and heuristics instead.
2. It underpins security. All of modern cryptography rests on complexity assumptions — RSA is safe only because we believe factoring is hard.
3. It is a placement/interview differentiator. "Is this problem NP-complete, and how would you cope?" is a real senior-engineer interview question.
4. It is intellectually spectacular. P vs NP carries a million-dollar prize and would reshape mathematics, AI and medicine if resolved.

Prerequisites

How to study this course

1. Learn the definitions cold. Half the exam marks are for stating P, NP, NP-hard, NP-complete, reductions and Cook–Levin precisely. Sloppy definitions lose marks fast.
2. Practise reductions on paper. Reductions are the "problems" of this subject — the gadget constructions in Unit 3 must be reproduced, not just recognised.
3. Keep a "class membership" table. Every time you meet a problem (sorting, SAT, CLIQUE, TQBF...), note its class. The table is your revision sheet.
4. Always check both directions. An NP-completeness proof needs membership in NP and NP-hardness — students routinely forget the first half.

Notation you will use all semester

What a typical end-term paper looks like

Two habits this table should trigger immediately: definitions are recall marks (bank them early), reductions are practice marks (earn them on paper, weekly — they cannot be crammed).

A four-week study plan that works

1. Week 1 — Unit 1: memorise the five asymptotic definitions; rebuild the class diagram from memory; write five O/Ω/Θ proofs with explicit constants.
2. Week 2 — Unit 2: trace the {0ⁿ1ⁿ} machine by hand; write the verifier ⟺ NTM equivalence argument once without notes.
3. Week 3 — Unit 3: reproduce the Cook–Levin outline; write the SAT → 3-SAT and 3-SAT → CLIQUE reductions from a blank page.
4. Week 4 — Unit 4 + revision: the class map, the P = NP consequences table, one approximation proof — then attack the revision lesson's question bank.

Self-check before you begin

1. Can you state, without looking, the difference between solving a problem and verifying a proposed solution?
2. Why does a 2ⁿ-time algorithm not become practical when computers get 1000× faster?
3. What two things must be shown to prove a problem NP-complete?
4. Which unit of this course proves the first NP-complete problem exists, and what is that problem?

Unit 1: Time & Space Complexity and Big-O Notation

1.1 What exactly are we measuring?

For an algorithm A and input of size n (bits, array length, number of vertices — state your convention!):

• Time complexity T(n): the maximum number of basic steps A performs on any input of size n — the worst case, expressed as a function of n.
• Space complexity S(n): the maximum number of memory cells A uses beyond the input.

We measure growth rates, not stopwatch seconds: hardware changes constants, but the growth rate is a property of the algorithm itself.

1.2 Big-O and its siblings — the formal definitions

Worked proof (exam staple). Show 3n² + 10n + 5 = O(n²): For n ≥ 1, 3n² + 10n + 5 ≤ 3n² + 10n² + 5n² = 18n². Take c = 18, n₀ = 1. ∎

Useful manipulation rules: drop constants and lower-order terms; O(f) + O(g) = O(max(f,g)); O(f)·O(g) = O(f·g); logarithm bases don't matter (log₂n = Θ(log₁₀n)).

1.3 The growth-rate ladder

O(1) ⊂ O(log n) ⊂ O(√n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(n³) ⊂ O(2ⁿ) ⊂ O(n!)
└──────────────── polynomial: "tractable" ────────────────┘ └─ exponential: "intractable" ─┘

Why the polynomial/exponential split is the dividing line — let one step take 1 µs and watch n grow:

Doubling CPU speed adds +1 to the n an exponential algorithm can handle. No hardware will ever rescue 2ⁿ — that is the Cobham–Edmonds thesis: tractable = polynomial time.

1.4 Space complexity and its relationship to time

• Space can be reused; time cannot. That asymmetry makes space classes behave differently.
• A machine running in time T(n) can touch at most T(n) cells: TIME(f) ⊆ SPACE(f).
• A machine using space S(n) ≥ log n has at most 2^O(S(n)) distinct configurations, so it either halts within that bound or loops forever: SPACE(f) ⊆ TIME(2^O(f)).

Important space classes to recognise now (Unit 4 returns to them): L = O(log n) space, PSPACE = polynomial space.

1.5 Decision problems and languages

Complexity theory standardises everything as decision problems — questions with YES/NO answers — encoded as languages:

L = { x ∈ {0,1}* : the answer for instance x is YES }

"Solve the problem" = "decide membership in L". Examples:

• PRIME = { ⟨n⟩ : n is prime }
• HAMPATH = { ⟨G⟩ : graph G has a Hamiltonian path }

Optimisation problems convert to decision versions by adding a threshold k ("is there a tour of cost ≤ k?") — and the decision version is easier-or-equal, so hardness of the decision version implies hardness of optimisation.

1.6 Worst, best, average — and why worst case rules

Complexity theory is built on the worst case because guarantees must hold for every input — an adversary picks the input, you pick the algorithm.

1.7 Deriving Big-O from code — three worked patterns

Pattern 1 — nested loops: count iterations.

for i = 1 to n:
    for j = 1 to i:
        O(1) work

The inner body runs 1 + 2 + ... + n = n(n+1)/2 times → Θ(n²). Rule: sum the iteration counts exactly, then keep the dominant term.

Pattern 2 — the halving loop.

i = n
while i > 1:   i = i / 2

After k passes i = n/2ᵏ; the loop stops when n/2ᵏ ≤ 1, i.e. k ≥ log₂ n → Θ(log n). Any loop whose control variable is multiplied or divided by a constant each pass is logarithmic.

Pattern 3 — recursion via recurrences. Binary search satisfies T(n) = T(n/2) + O(1) → O(log n). Merge sort satisfies T(n) = 2T(n/2) + O(n): unrolling gives log n levels, each costing O(n) in total → O(n log n).

Master theorem (state it for recurrence questions). For T(n) = a·T(n/b) + f(n) with a ≥ 1, b > 1, let c = log a / log b (so nᶜ counts the leaves of the recursion tree):

Check on merge sort: a = 2, b = 2 → c = 1, f(n) = n = Θ(n¹) → case 2 → Θ(n log n) ✓.

1.8 Comparing growth rates by limits (a fast exam tool)

Evaluate lim f(n)/g(n) as n → ∞:

Example: is n log n = O(n^1.5)? lim (n log n)/n^1.5 = lim (log n)/√n = 0 → yes, and strictly. Standard facts to quote: log n grows slower than every nᵉ (ε > 0); every polynomial nᵏ grows slower than every exponential cⁿ (c > 1); every cⁿ grows slower than n!.

1.9 A worked Ω and Θ proof

Show n²/2 − 3n = Θ(n²). Upper bound: n²/2 − 3n ≤ n² for all n ≥ 1 (take c₂ = 1). Lower bound: n²/2 − 3n ≥ n²/4 ⟺ n²/4 ≥ 3n ⟺ n ≥ 12 (take c₁ = 1/4, n₀ = 12). Both directions exhibited with explicit constants — exactly the presentation the exam wants. ∎

Exam pointer

• "Prove from the definition that f = O(g)" (4–5 marks): produce explicit c and n₀, verify the inequality line by line, finish with ∎. Limits are not allowed if the question says from the definition.
• "Arrange functions in increasing order of growth" (4 marks): a typical set is 1, log n, √n, n, n log n, n², 2ⁿ, n!; justify one or two adjacent pairs with the limit test.
• "Distinguish time vs space complexity / worst vs average case" (short note): reproduce the tables of §1.4 and §1.6.

Self-check

1. Give explicit c and n₀ proving 5n³ + 2n = O(n³).
2. Why does the base of a logarithm not matter inside O(·)?
3. State the two containments connecting TIME and SPACE and give the one-line reason for each.
4. Convert the optimisation problem "find the largest clique in G" into a decision problem.
5. True or false: f = O(g) and f = Ω(g) together imply f = Θ(g)? (True — that is the definition of Θ.)

Frequently asked questions

Is the Complexity Theory course really free?

Yes. The entire Complexity Theory course on Siksha Sarovar is free to read with no account required. You can optionally sign in with Google to save your progress.

Do I get a certificate for Complexity Theory?

Yes — finish the lessons and pass the quiz to earn a free, verifiable certificate you can share on LinkedIn or with recruiters.

Can I run code while learning?

Yes. The built-in online compiler runs C, C++, Python, Java, PHP, JavaScript, C# and SQL directly in your browser — no installation needed.