Divide and Conquer Algorithms and Asymptotic Analysis

a) Divide and Conquer Idea (≤ 8 sentences)

Split the array into two halves around a middle index. Recursively compute the maximum subarray sum entirely in the left half and entirely in the right half. Also, compute the best “crossing” subarray that ends in the left half (best suffix of left) and continues into the right half (best prefix of right). The maximum subarray for the whole array is the maximum of these three values. The crossing sum can be found in linear time by scanning leftward from the middle to get a max suffix and scanning rightward from the middle + 1 to get a max prefix. Use this recursively until the base case of a single element is reached.

b) Recurrence and Asymptotic Time

Let T(n) be the running time on n items. We split into two subproblems of size n/2 and spend linear time to compute the crossing sum and combine:

T(n) = 2T(n/2) + Θ(n), where T(1) = Θ(1).

By the Master Theorem, where a = 2 and b = 2, we find that n^{log_b a} = n¹ = n. Since f(n) = Θ(n), the complexity is:

T(n) = Θ(n log n)

c) Asymptotic Growth Rates

Here are the Θ rates (dominant growth terms). I interpret spacing as multiplication and exponents as usual:

• a) n³ + 2n² + 7n²√n + 2 = Θ(n³)
• b) 12n² log₂ n + n^2.5 + log n + 5n = Θ(n^2.5)
• c) 0.5ⁿ + n + 31 = Θ(n)
• d) n²2ⁿ + n4ⁿ + n³ log n = Θ(n · 4ⁿ)

d) Single Non-Duplicate in a Sorted Array

Here’s a clean divide and conquer (binary search) solution tailored to 1-indexed arrays.

Idea (few sentences):
In a sorted array where all values appear exactly twice except one, pairs occupy consecutive positions. Before the single element, each pair starts at an odd index (1,2), (3,4), &dots;; after the single element, the pairing shifts so the first of a pair lands on an even index. Use binary search on indices: at mid, compare with its neighbor on the “pair side” (mid + 1 if mid is odd, mid - 1 if mid is even). If the comparison matches, the single lies to the right; otherwise, it lies to the left (including mid). This halves the search space each step.

function singleNonDuplicate(A, n):
    lo ← 1
    hi ← n
    while lo < hi:
        mid ← floor((lo + hi) / 2)
        if mid is odd:
            if A[mid] == A[mid + 1]:
                lo ← mid + 2  # skip this pair; single is to the right
            else:
                hi ← mid      # mismatch ⇒ single is at/before mid
        else:
            if A[mid] == A[mid - 1]:
                lo ← mid + 1  # matched pair ends at mid ⇒ go right
            else:
                hi ← mid      # mismatch ⇒ single is at/before mid
    return A[lo]

Each step discards about half the remaining indices, doing O(1) work (a couple of comparisons). Thus, the recurrence is T(n) = T(n/2) + Θ(1), giving T(n) = Θ(log n) time and Θ(1) extra space (iterative).

e) Maximum Stock Gain via Divide and Conquer

Idea (few sentences):
Split the array into two halves. Recursively compute:
(1) the best gain inside the left half,
(2) the best gain inside the right half, and
(3) the best cross gain, where the buy index is in the left half and the sell index is in the right half.
The cross gain is simply maxRight - minLeft, so each recursive call should also return the minimum value and maximum value of its segment. Combine with:

function solve(A, L, R):  # returns (best_gain, min_value, max_value)
    if L == R:
        return (0, A[L], A[L])

    mid = floor((L + R) / 2)
    (gL, minL, maxL) = solve(A, L, mid)
    (gR, minR, maxR) = solve(A, mid + 1, R)

    crossGain = maxR - minL
    bestGain  = max(gL, gR, crossGain)
    minVal    = min(minL, minR)
    maxVal    = max(maxL, maxR)

    return (bestGain, minVal, maxVal)

function maximumGain(A, n):
    (ans, _, _) = solve(A, 1, n)
    return ans

The recurrence is T(n) = 2T(n/2) + Θ(1), which results in T(n) = Θ(n).

f) Complexity Analysis of Specific Algorithms

Algorithm A

The outer loop runs n² times; the middle loop runs a constant x = 10 times; the inner loop runs √n times. Total prints = n² · 10 · √n = Θ(n^2.5).

Algorithm B

For each of the n iterations of the outer loop, the while loop multiplies j by 3 each time (1, 3, 9, &dots;) until j ≥ n. That’s Θ(log₃ n) = Θ(log n) prints per outer iteration, so the total is Θ(n log n).

Algorithm C

The recurrence for the number of prints is T(n) = 4T(n/2) + Θ(1) (four recursive calls on n/2 plus one constant-time print when n ≥ 2; the base case prints once). By the Master Theorem with a = 4 and b = 2, we find n^{log_b a} = n². Since f(n) = Θ(1), we get T(n) = Θ(n²).