Divide and Conquer

Master Theorem

Master theorem. Let a ≥ 1, b ≥ 2, and c ≥ 0 and suppose that T(n) is a function on the non-negative integers that satisfies the recurrence

$\displaystyle T(n) = aT(\frac{n}{b}) + \Theta(n^c)$

with T(0) = 0 and T(1) = Θ(1), where n / b means either ⎣n / b⎦ or ⎡n / b⎤. Then,

• If $c > log_ba$, then $T (n) = Θ(n^c )$. (Combining cost more than subproblem)

• If $c = log_ba$, then $T(n) = Θ(n^c log n)$.

• If $c < log_ba$, then $T(n) = Θ(n^{log_ba} )$. (Combining cost less than subproblem)

Binary Search

For a sorted array, find the given item

1. find the mid item, compare it to the target

2. less than goes to left subarray; $hi = mid - 1$

3. bigger than goes to right subarray; $lo = mid + 1$

4. continue util find it at mid or find none

5. After loop, $i > j$and will return -1

• Divide and conquer happens at the same time, there is no combining, so $c=0$

• $b=2$ divide

• $a = 1$becuase we only consider one subproblem

• $c == log_21 == 0, T(n) = \Theta(n^clogn) = \Theta(logn)$

Bisect

Bisect_left

Given an array a sorted nums and an element target , find the index such that all the elements to the left are smaller than target , all the elements to the right and the current element are bigger than or equal to target.

• The index returned can be 0 or len(nums)

input:   [ 1, 2, 3] , 0
output:  0

input:   [ 1, 2, 3], 4
output:  4

1. Find the middle item, compare it to the target, with $lo = 0, hi = len(nums)$

2. If less than, consider right subarray by $lo = mid + 1$

3. If bigger than or equal to, consider the left subarray; however since this current element can be the index we are looking for, so we include the $mid, hi=mid$

4. After all scanning, return either lo or hi since $lo == hi$

// all i < lo, arr[i] < x
int bisect_left(int arr, int x){
    int lo = 0, hi = arr.length, mid;
    while (lo < hi):
        mid = (lo+hi) / 2;
        if (a[mid] < x) lo = mid+1;
        else hi = mid;
    return lo;

}      

Bisect_right

Given an array a sorted nums and an element target , find the index such that all the elements to the left are smaller than or equal to target , all the elements to the right and the current element are bigger than target.

• The index returned can be 0 or len(nums)

input:   [ 1, 2, 3] , 0
output:  0

input:   [ 1, 2, 3], 4
output:  4

1. Find the middle item, compare it to the target, with $lo = 0, hi = len(nums)$

2. If less than or equal to, consider right subarray; however since this current element can be the index we are looking for, so we include the $mid, hi=mid$

3. If bigger than, consider the left subarray $lo = mid + 1$

4. After all scanning, return either lo or hi since $lo == hi$

// all i >= lo, arr[i] > x
int bisect_left(int arr, int x){
    int lo = 0, hi = arr.length, mid;
    while (lo < hi):
        mid = (lo+hi) / 2;
          if (a[mid] <= x) lo = mid + 1;
          else hi = mid; 

//        if (a[mid] > x) hi = mid;
//        else lo = mid + 1;
    return lo;

}      

Randomized Quicksort

Given an array of $n ≥ 2$ distinct elements $a_1 < a_2 <\ldots< a_n$ the probability that $a_i$ and $a_j$ are compared during randomized quicksort is $\displaystyle \frac{2}{j-i+1}$

Hint: think about the subarray $a_i < a_2 <\ldots< a_j$, choosing anything other than $a_i$or $a_j$will never compare $a_i$and $a_j$anymore, because they are split into different branches of the chosen pivot element. To chose either $a_i$or $a_j$ the probabilty is $\displaystyle \frac{2}{j-i+1}$.

Proof:

Step 1, n == 2: $a_1$and $a_2$will be definitely compared, and the probability is 1.

Step 2, $n\geq 3$:

• To choose either $a_i$or $a_j$is with prob of $\displaystyle \frac{2}{n}$

• To choose one outside $a_i ... a_j$is with prob of $\displaystyle \frac{n - (j-i+1)}{n}$, then $a_i$and $a_j$will be partitioned into the same branch of the chosen pivot element. By induction, that probability of them get compared within that subarray is $\displaystyle \frac{2}{j-i + 1}$

• Add them together, proof is concluded.

$\displaystyle \frac{2}{n} + \frac{n - (j-i+1)}{n} * \displaystyle \frac{2}{j-i + 1} = \frac{2}{n} + (1 - \frac{ (j-i+1)}{n})*\frac{2}{j-i + 1} = \frac{2}{n} + \frac{2}{j-i + 1} - \frac{2}{n} = \frac{2}{j-i + 1}$

$f(n) = log_2n = n^c$ $\space c = log_{n}^{log_2{n}} =$