Skip to main content
Code ScholarsCodeScholars

DSA Foundations · Analysis

Master Theorem

The Master Theorem gives students a shortcut for many divide-and-conquer recurrences once they understand what the recurrence is measuring.

Enroll NowText UsContact Code ScholarsFull DSA Course

Student Focus

This is taught as an advanced analysis tool after students can trace recursion confidently.

Guided Lesson Notes

Understanding Master Theorem

Master Theorem focuses on algorithmic reasoning, correctness, and choosing the right structure before writing code. The Master Theorem gives students a shortcut for many divide-and-conquer recurrences once they understand what the recurrence is measuring.

Model: start with inputs and outputs, then decide what information must be remembered at each step.

Invariant: every step must preserve the meaning of the variables and move measurably closer to the goal.

Implementation: pseudocode, traces, helper functions, tests, and complexity checks.

Use Master Theorem when the problem is less about syntax and more about selecting a strategy that scales.

Visual Model

A small picture for Master Theorem

1

Model

2

Trace

3

Analyze

Key Ideas

  • Recursive subproblem count
  • Subproblem size shrinkage
  • Combine-work cost

Practice Prompts

  • Write recurrences for binary search and merge sort.
  • Identify which part of a divide-and-conquer algorithm controls the final growth rate.

Vocabulary

Terms students should be able to say clearly

Input

The data the algorithm receives.

Output

The result the algorithm must produce.

Precondition

A fact that must be true before the algorithm runs.

Correctness

Why the algorithm always returns the required answer.

Complexity

How time and memory grow with input size.

Tradeoff

A choice where improving one cost may worsen another.

Worked Example

Worked example: tracing Master Theorem

Trace a small input, focusing on recursive subproblem count.

  1. 1Write a small input where Master Theorem is clearly useful.
  2. 2Label the part of the input related to Recursive subproblem count.
  3. 3Perform one operation and explain which invariant is still true afterward.
  4. 4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
  5. 5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

OperationTypical CostReason
Trace a small inputSmall nUse a tiny example to understand state changes before coding.
Implement the core ideaDepends on topicChoose data structures that match the operations you need.
Analyze growthBig-OExplain how work changes as the input gets larger.

Common Mistakes

What to watch while practicing

  • Coding before drawing the structure or state changes.
  • Forgetting the invariant that makes the algorithm correct.
  • Testing only the sample input and skipping boundary cases.
  • Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Master Theorem interview problem: Maximum Product Subarray

Interview medium

Problem

Given an integer array that may contain negative values and zeros, find the maximum product of a non-empty contiguous subarray.

Input

The first line contains n. The second line contains n integers.

Output

Print the maximum product.

Sample Input

6
-2 3 -4 0 -1 -2

Sample Output

24

Why the sample works

The subarray -2, 3, -4 has product 24, which is the maximum.

Approach

  1. 1Track both the maximum and minimum product ending at the current index.
  2. 2A negative value can turn the minimum product into the new maximum product.
  3. 3Swap the two trackers when the current value is negative.
  4. 4Update the global best after processing each value.

O(n) time and O(1) extra space.

Java Solution

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long currentMax = sc.nextLong();
    long currentMin = currentMax;
    long answer = currentMax;

    for (int i = 1; i < n; i++) {
      long x = sc.nextLong();
      if (x < 0) {
        long temp = currentMax;
        currentMax = currentMin;
        currentMin = temp;
      }

      currentMax = Math.max(x, currentMax * x);
      currentMin = Math.min(x, currentMin * x);
      answer = Math.max(answer, currentMax);
    }

    System.out.println(answer);
  }
}

Python Solution

n = int(input())
a = list(map(int, input().split()))

current_max = a[0]
current_min = a[0]
answer = a[0]

for x in a[1:]:
    if x < 0:
        current_max, current_min = current_min, current_max

    current_max = max(x, current_max * x)
    current_min = min(x, current_min * x)
    answer = max(answer, current_max)

print(answer)

Practice Challenge

Make the idea your own

Create a two-minute explanation of Master Theorem: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free SessionText UsOpen Online Compiler