Divide and Conquer

DSA · Algorithm Techniques

Theory

Divide and conquer splits a problem into smaller independent sub-problems of the same type, solves them recursively, and combines their answers. Merge sort, quick sort, binary search and fast exponentiation all follow this pattern. The running time is often described by recurrences such as T(n) = 2T(n/2) + O(n), which solves to O(n log n).

Why we use it

Splitting the work reduces complexity dramatically and allows parallel processing of independent parts.

When to use it

Use it for sorting, searching, fast power, counting inversions, closest pair of points and large-scale parallel computations (MapReduce follows the same idea).

How it works

  1. solve(problem)
  2. Small enough? Yes: Solve directly. No: Divide into subproblems.
  3. Solve each subproblem recursively
  4. Combine the results
  5. Return

Syntax

solve(problem):
    if small: return direct answer
    parts = split(problem)
    results = [solve(p) for p in parts]
    return combine(results)

T(n) = 2T(n/2) + O(n)  ->  O(n log n)

Example

def power(base, exp):
    if exp == 0:
        return 1
    half = power(base, exp // 2)
    if exp % 2 == 0:
        return half * half
    return half * half * base

def max_subarray(nums, lo, hi):
    if lo == hi:
        return nums[lo]
    mid = (lo + hi) // 2
    best_left = total = float("-inf")
    s = 0
    for i in range(mid, lo - 1, -1):
        s += nums[i]; best_left = max(best_left, s)
    best_right, s = float("-inf"), 0
    for i in range(mid + 1, hi + 1):
        s += nums[i]; best_right = max(best_right, s)
    return max(max_subarray(nums, lo, mid), max_subarray(nums, mid + 1, hi), best_left + best_right)

print("2^30 =", power(2, 30))
data = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Max subarray sum:", max_subarray(data, 0, len(data) - 1))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic