Decomposition Formula

The Formula

P \rightarrow \{P_1, P_2, \ldots, P_k\} \quad \text{then} \quad S = f(S_1, S_2, \ldots, S_k)

When to use: Eating an elephant: one bite at a time. Big problems become many small ones.

Quick Example

Building a house: foundation, framing, plumbing, electrical, finishing—each is a sub-problem.

Notation

A problem P decomposes into sub-problems P_1, P_2, \ldots, P_k. Each P_i is solved independently, and solutions combine via an integration step S = f(S_1, S_2, \ldots, S_k).

What This Formula Means

Breaking a complex problem into smaller, independently-solvable parts that combine into a complete solution.

Eating an elephant: one bite at a time. Big problems become many small ones.

Formal View

Decomposition partitions a problem P into sub-problems P_1, P_2, \ldots, P_k such that solving all sub-problems and combining their solutions yields a solution to P.

Worked Examples

Example 1

easy
You need to plan a school sports day. Decompose this problem into smaller sub-problems.

Solution

  1. 1
    Step 1: Identify the major areas: events/activities, equipment, scheduling, participants, venue.
  2. 2
    Step 2: Break each area down further — e.g., Events: choose sports, set rules, assign referees. Scheduling: set times, allocate fields, plan breaks.
  3. 3
    Step 3: Each sub-problem is now small enough to tackle individually.

Answer

Sub-problems: choose events, organise equipment, create schedule, register participants, prepare venue, plan prizes.
Decomposition breaks a complex problem into smaller, manageable parts. Each part can be solved independently, making the overall problem less overwhelming.

Example 2

medium
Decompose the task of building a simple calculator program.

Common Mistakes

  • Splitting a problem into parts that are still too large or too intertwined to solve independently
  • Forgetting to plan how the sub-solutions will be recombined into the final answer
  • Over-decomposing into too many tiny parts, creating unnecessary complexity in integration

Common Mistakes Guide

If this formula feels simple in isolation but keeps breaking during real problems, review the most common errors before you practice again.

Algorithm Mistakes

Why This Formula Matters

Decomposition makes overwhelming problems tractable and is the core of systematic problem-solving. Every large software system—from web browsers to operating systems—is built by decomposing the problem into manageable modules that teams can develop independently.

Frequently Asked Questions

What is the Decomposition formula?

Breaking a complex problem into smaller, independently-solvable parts that combine into a complete solution.

How do you use the Decomposition formula?

Eating an elephant: one bite at a time. Big problems become many small ones.

What do the symbols mean in the Decomposition formula?

A problem P decomposes into sub-problems P_1, P_2, \ldots, P_k. Each P_i is solved independently, and solutions combine via an integration step S = f(S_1, S_2, \ldots, S_k).

Why is the Decomposition formula important in CS Thinking?

Decomposition makes overwhelming problems tractable and is the core of systematic problem-solving. Every large software system—from web browsers to operating systems—is built by decomposing the problem into manageable modules that teams can develop independently.

What do students get wrong about Decomposition?

The parts must be truly independent or have clear dependencies.

← Back to Decomposition See All Examples Common Mistakes Practice Problems