Skip to content
ComplexityX

Settings

Server engine

Loading…

Use my own key optional

The key stays in this browser's local storage and is sent only to this app's /api/analyze route, which forwards it to the provider. It is never stored on the server.

All patterns

Divide and Conquer

Split, solve halves independently, combine.

time O(n log n) for the classic 2-way splitspace O(n) plus O(log n) stack

What it is

Break the problem into independent subproblems of the same kind, solve them recursively and merge results. The Master theorem gives the cost: T(n) = a·T(n/b) + f(n).

When to reach for it

  • Sorting
  • Counting inversions
  • Closest pair, maximum crossing subarray
  • Tree-shaped recursion with balanced halves

Clues in the problem

  • Two recursive calls on n/2
  • A linear merge step

Template

def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
l, r = merge_sort(a[:mid]), merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(l) and j < len(r):
if l[i] <= r[j]:
out.append(l[i]); i += 1
else:
out.append(r[j]); j += 1
return out + l[i:] + r[j:]

Practice problems

  • Merge Sort
  • Count of Smaller Numbers After Self
  • Kth Largest (quickselect)
  • Maximum Subarray (D&C form)

Common mistakes

  • Slicing copies that hide extra O(n) per level
  • Unbalanced splits degrading to O(n²)
  • Missing base case