# 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)$$.&#x20;
* &#x20;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$$

```java
// 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$$

```java
// 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

{% hint style="warning" %}
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}$$.&#x20;
{% endhint %}

{% hint style="success" %}
Proof:

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

Step 2, $$n\geq 3$$:&#x20;

* 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}$$
{% endhint %}

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