Skip to content

Divide and Conquer Trees

The Shape of the Tree IS the Complexity

Every divide-and-conquer algorithm builds a recursion tree. We saw this in the Master Theorem lesson. Now we'll look at three specific algorithms — merge sort, quicksort, and binary search — and show that the shape of their recursion trees directly determines their performance.

The punchline: a balanced tree gives you \(O(n \log n)\). A skewed chain gives you \(O(n^2)\). A single path gives you \(O(\log n)\). No formulas needed — just look at the tree.

Merge sort produces a balanced tree, quicksort worst case produces a chain

Merge Sort: The Perfectly Balanced Tree

Merge sort always splits the array exactly in half. This produces a perfectly balanced binary tree.

For \(n = 8\) elements [8, 3, 5, 1, 4, 2, 7, 6]:

                    [8,3,5,1,4,2,7,6]              merge: 8 comparisons
                   /                 \
           [8,3,5,1]              [4,2,7,6]         merge: 4+4
           /       \              /       \
        [8,3]     [5,1]       [4,2]     [7,6]       merge: 2+2+2+2
        /  \      /  \        /  \      /  \
      [8]  [3]  [5]  [1]   [4]  [2]  [7]  [6]      base cases

Each level of the tree processes all \(n\) elements exactly once (during the merge step). The tree has \(\log_2 8 = 3\) levels. Total work: \(n \cdot \log n = 24\).

The tree is balanced because merge sort controls the split point — it always picks the middle. No matter what the input looks like, the tree has the same shape. That's why merge sort is always \(O(n \log n)\).

Level Arrays being merged Total elements processed
3 (bottom) 4 merges of size 2 8
2 2 merges of size 4 8
1 1 merge of size 8 8

Quicksort: The Random Tree

Quicksort partitions the array around a pivot. The pivot's position determines the split — and the split determines the tree shape.

Best Case: Balanced Split

If the pivot always lands in the middle, quicksort produces the same balanced tree as merge sort:

                    [4,2,7,1,5,8,3,6]
                   /                 \
           [2,1,3]       4       [7,5,8,6]
           /     \                /     \
         [1]  2  [3]         [5,6]  7  [8]
                              / \
                            [5] 6

Balanced tree. \(O(n \log n)\).

Worst Case: Pivot Is Always the Smallest (or Largest)

If you always pick the minimum element as pivot (this happens with sorted input and "first element" pivot selection):

[1, 2, 3, 4, 5, 6, 7, 8]

[1] -> [2, 3, 4, 5, 6, 7, 8]          partition: 8 comparisons
        [2] -> [3, 4, 5, 6, 7, 8]      partition: 7 comparisons
                [3] -> [4, 5, 6, 7, 8]  partition: 6 comparisons
                        ...             ...
                            [7] -> [8]  partition: 2 comparisons

The tree degenerates into a chain — each node has only one non-empty child:

[1,2,3,4,5,6,7,8]    work: 8
         \
  [2,3,4,5,6,7,8]    work: 7
           \
    [3,4,5,6,7,8]    work: 6
             \
      [4,5,6,7,8]    work: 5
               \
        [5,6,7,8]    work: 4
               \
          [6,7,8]     work: 3
              \
           [7,8]      work: 2
              \
             [8]      work: 1

Total work: \(8 + 7 + 6 + \cdots + 1 = \frac{n(n+1)}{2} = 36\). That's \(O(n^2)\).

Side-by-Side Comparison for n = 8

Property Balanced tree Chain
Depth \(\log_2 8 = 3\) \(8 - 1 = 7\)
Work at level \(d\) \(\approx n\) \(n - d\)
Total work \(n \log n = 24\) \(n(n+1)/2 = 36\)
Complexity \(O(n \log n)\) \(O(n^2)\)

Same algorithm, different tree shapes, different complexities. Randomized pivot selection makes the balanced case overwhelmingly likely — the expected depth is \(O(\log n)\).

Binary Search: A Path, Not a Tree

Binary search doesn't branch. At each step, you go left OR right — never both. The "recursion tree" is a single path from root to leaf.

Searching for 5 in [1, 2, 3, 4, 5, 6, 7, 8]:

              [1,2,3,4,5,6,7,8]  mid=4, target>4, go right
                        \
               [5,6,7,8]        mid=6, target<6, go left
                /
             [5]                 mid=5, target==5, found

Three comparisons. The path has length \(\log_2 8 = 3\).

This is also why binary search IS a path in a BST. If you built a balanced BST from [1, 2, 3, 4, 5, 6, 7, 8]:

            4
          /   \
        2       6
       / \     / \
      1   3   5   7
                   \
                    8

Searching for 5: start at 4, go right to 6, go left to 5. The exact same path.

Binary search = walking a path from root to target in an implicit balanced BST. The array is the BST, the midpoint formula gives you the root of each subtree, and going left/right in the array is going left/right in the tree.

The Unifying View

Algorithm Tree shape Branching Depth Work per level Total
Merge sort Balanced binary 2 children \(\log n\) \(n\) \(O(n \log n)\)
Quicksort (best) Balanced binary 2 children \(\log n\) \(n\) \(O(n \log n)\)
Quicksort (worst) Chain 1 child \(n\) \(n - d\) \(O(n^2)\)
Binary search Path 1 child \(\log n\) \(O(1)\) \(O(\log n)\)

The tree shape encodes everything:

  • Depth = how many levels of recursion = the \(\log n\) or \(n\) factor.
  • Width = how much work per level = the \(n\) or \(O(1)\) factor.
  • Balance = whether the algorithm is efficient or degenerate.

When someone asks "why is merge sort \(O(n \log n)\)?" — draw the tree. When someone asks "why can quicksort be \(O(n^2)\)?" — draw the chain. When someone asks "why is binary search \(O(\log n)\)?" — draw the path.

The tree shape IS the algorithm's complexity. Once you can draw the tree, you can read the answer.

Try It

The starter code implements binary search on a sorted array of 8 elements.

Predict before running: How many comparisons does it take to find 5? Draw the implicit BST and trace the path. (Answer: 3 comparisons — check 4, check 6, check 5.)

Challenge: What's the maximum number of comparisons for binary search on an array of size \(n = 1000\)? (Answer: \(\lceil \log_2 1000 \rceil = 10\).)

Challenge 2: Add a comparison counter to the merge sort snippet. For \(n = 8\), the total should be close to \(n \log_2 n = 24\). For \(n = 16\), it should be close to \(64\). Verify.

Edge Cases to Watch For

  • Already sorted input for quicksort: With "first element" pivot selection, a sorted array produces the worst-case chain. Every partition puts 0 elements on one side and \(n-1\) on the other. Use randomized pivot selection to avoid this.
  • All elements identical: Quicksort with naive partitioning degenerates to \(O(n^2)\) because every element equals the pivot. Three-way partitioning (Dutch National Flag) handles this by grouping equal elements together.
  • Binary search mid overflow: (left + right) / 2 overflows when both are large positive integers. Use left + (right - left) / 2 instead.

Problems

Problem Link Difficulty
LC 912 — Sort an Array leetcode.com/problems/sort-an-array Medium
LC 704 — Binary Search leetcode.com/problems/binary-search Easy
LC 215 — Kth Largest Element (Quickselect) leetcode.com/problems/kth-largest-element-in-an-array Medium