Divide and Conquer

2026-11-18

notes / Algorithms-1

Algorithms-1


Master Method

T(n)=aT(n/b)+f(n)

a≥1 and b>1 and f(n) is asymptotically positive

  1. if f(n)=O(n(logba)−ϵ) for ϵ>0 then T(n)=Θ(nlogba)
  2. if f(n)=Θ(nlogba) then T(n)=Θ(nlogbalgn)
  3. if f(n)=Ω(n(logba)+ϵ) and af(n/b)≤cf(n) for c<1 then T(n)=Θ(f(n))

Merge Sort

def Merge_Sort(A, p, r):
if p < r:
    q = floor((p + r) / 2)
    Merge_Sort(A, p, q)
    Merge_Sort(A, q + 1, r)
    Merge(A, p, q, r)   
    
def Merge(A, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    L[n1]
    R[n2]
    for i = 0; i < n1; i++:
        L[i] = A[p + i]
    for i = 0; i < n2; i++:
        R[i] = A[q + i + 1]
    L[n1] = INT_MAX
    R[n2] = INT_MAX
    i = 0
    j = 0
    for k = p to r:
        if L[i] <= R[j]:
            A[k] = L[i]
            i++
        else:
            A[k] = R[i]
            j++

Quicksort

def Quicksort(A, p, r):
    if p < r:
        q = Partition(A, p, r)
        Quicksort(A, p, q - 1)
        Quicksort(A, q + 1, r)
        
def Partition(A, p, r):
    x = A[r]
    i = p - 1
    for (j = p; j < r; j++):
        if (A<=x):
            i++
            swap(A[i], A[j])
    swap(A[i+1], A[r])
    return i + 1

Max Subarray

  1. Divide and Conquer
def Max_Subarray(A, l, r):
    if l == r
        return A[r]
    m = (l + r) / 2
    l_sum = Max_Subarray(A, l, m)
    r_sum = Max_Subarray(A, m + 1, r)
    c_sum = Max_Crossing(A, l, m, r)
    return MAX(l_sum, r_sum, c_sum)
def Max_Crossing(A, l, m, r):
    l_sum = INT_MIN
    sum = 0
    for i = m to l
        sum += A[i]
        l_sum = MAX(sum, l_sum)
    r_sum = INT_MIN
    sum = 0
    for i = m + 1 to r
        sum += A[i]
        r_sum = MAX(sum, r_sum)
    return l_sum + r_sum
  1. Sliding Window
def Kadane(A, n):
    best_sum = INT_MIN
    curr_sum = 0
    for i = 0 to n
        curr_sum = MAX(A[i], curr_sum + A[i])
        best_sum = MAX(curr_sum, best_sum)
    return best_sum