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

T(n)=aT(nb)+Θ(nc)\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>logbac > log_ba, then T(n)=Θ(nc)T (n) = Θ(n^c ). (Combining cost more than subproblem)

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

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

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−1hi = mid - 1

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

  4. continue util find it at mid or find none

  5. After loop, i>ji > jand will return -1

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

  • b=2b=2 divide

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

  • c==log21==0,T(n)=Θ(nclogn)=Θ(logn)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)lo = 0, hi = len(nums)

  2. If less than, consider right subarray by lo=mid+1lo = 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=midmid, hi=mid

  4. After all scanning, return either lo or hi since lo==hilo == 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)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=midmid, hi=mid

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

  4. After all scanning, return either lo or hi since lo==hilo == 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

f(n)=log2n=ncf(n) = log_2n = n^c  c=lognlog2n=\space c = log_{n}^{log_2{n}} =

Last updated

Was this helpful?