Allocate Minimum Pages Binary Search on Answer in DSA Go - Time & Space Complexity

Time Complexity: Allocate Minimum Pages Binary Search on Answer

O(n * log m)

Understanding Time Complexity

We want to find how fast the binary search approach solves the problem of allocating minimum pages.

Specifically, how the number of steps grows as the number of books or pages increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func isPossible(books []int, students, mid int) bool {
    count := 1
    sum := 0
    for _, pages := range books {
        if pages > mid {
            return false
        }
        if sum+pages > mid {
            count++
            sum = pages
            if count > students {
                return false
            }
        } else {
            sum += pages
        }
    }
    return true
}

func allocateMinimumPages(books []int, students int) int {
    start, end := 0, 0
    for _, pages := range books {
        if pages > start {
            start = pages
        }
        end += pages
    }
    result := end
    for start <= end {
        mid := (start + end) / 2
        if isPossible(books, students, mid) {
            result = mid
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    return result
}

This code tries to find the smallest maximum number of pages assigned to any student by using binary search on the answer range.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The binary search loop that runs while narrowing the page range.
• How many times: The binary search runs about log of the sum of pages times.
• Inside each binary search step: The isPossible function loops through all books once (n times).
• Dominant operation: The repeated full traversal of the books array inside each binary search step.

How Execution Grows With Input

As the number of books (n) grows, each check scans all books once.

The binary search cuts the search space of possible page sums roughly in half each time.

Input Size (n)	Approx. Operations
10 books	About 10 * log(sum of pages) checks
100 books	About 100 * log(sum of pages) checks
1000 books	About 1000 * log(sum of pages) checks

Pattern observation: The total steps grow linearly with the number of books and logarithmically with the total pages.

Final Time Complexity

Time Complexity: O(n * log m)

This means the time grows linearly with the number of books and logarithmically with the sum of all pages.

Common Mistake

[X] Wrong: "The binary search alone makes this O(log n) time."

[OK] Correct: Each binary search step requires scanning all books to check feasibility, so the linear scan dominates.

Interview Connect

Understanding this time complexity helps you explain how binary search can be applied beyond simple arrays, showing problem-solving skills.

Self-Check

"What if we used a different feasibility check that skips some books? How would that affect the time complexity?"