MiniMax Using Divide & Conquer

Idea

MiniMax is a decision-making algorithm used in adversarial search (like games).
Using divide and conquer, we recursively split the game tree into two subproblems:

Left subtree → Maximizer’s choice
Right subtree → Minimizer’s choice

At each level:

Max level: choose max(left, right)
Min level: choose min(left, right)

The game tree is divided into two equal halves until we hit leaf nodes.

Procedure

cpp

int minimax(int arr[], int l, int r, bool isMax) {
    // Base case: when only 1 or 2 elements left
    if (r - l + 1 <= 2) {
        if (isMax) return max(arr[l], arr[r]);
        else return min(arr[l], arr[r]);
    }

    int mid = (l + r) / 2;

    // Divide into two equal problems
    int left  = minimax(arr, l, mid, isMax == false);
    int right = minimax(arr, mid + 1, r, isMax == false);

    // Combine result depending on Max or Min level
    if (isMax) return max(left, right);
    else return min(left, right);
}

Divide & Conquer Recurrence

Given:

T(n)=\begin{cases}T(n/2)+T(n/2)+c, & n>2\\ \text{constant}, & n=1,2\end{cases}

This simplifies to:

T(n)=2T(n/2)+c

Time Complexity

Recursion tree for min-max algorithm showing divide-and-conquer approach splitting array into halves across levels.

Taking :

T(n)=\left(c+2c+4c+\dots+2^{k-1}\cdot c\right)+2^{k}\cdot T(1)

T(n)=c\left(1+2+2^2+\cdot\cdot\cdot+2^{k-1}\right)+2^{k}\cdot A

The inside term is a geometric progression:

1+2+2^2+\cdot\cdot\cdot+2^{k-1}

This is GP with:

first term
common ratio
number of terms

GP Sum Formula

S_{k}=\frac{r^k - 1}{r - 1}

For

S_{k}=\frac{2^k - 1}{2 - 1}=2^{k}-1

T(n)=c\left(1+2+2^2+\cdot\cdot\cdot+2^{k-1}\right)+2^{k}\cdot A

T(n) = c\left(2^k - 1\right) + 2^k \cdot A

T(n) = c\cdot2^k - c + 2^k \cdot A

T(n) = 2^k \left(A + c \right) - c

T(n) = n(A + c) - c \quad \boxed{n = 2^k}

Asymptotically:

\boxed{T(n) = \Theta(n)}

Final Time Complexity

✔
✔ You process all leaf nodes once
✔ Divide & Conquer halves the problem but doubles calls → linear overall