<a href="https://colab.research.google.com/github/lmcanavals/algorithmic_complexity/blob/main/03_01_divide_and_conquer.ipynb" target="_parent"></a>

# Divide and Conquer

## Master Theorem

$$ T(n) = aT(\frac{n}{b}) + O(n^k) $$

So...

$$
T(n) = \begin{equation}
\left\{ 
  \begin{aligned}
    O(n^k)           && a < b^k\\
    O(n^k\,log\,n)   && a = b^k\\
    O(n^{log_b\,a})  && a > b^k
  \end{aligned}
  \right.
\end{equation}
$$

## Max element in list


```python
import random

a = list(range(30))
random.shuffle(a)
print(a)
```

    [13, 17, 9, 10, 5, 22, 15, 24, 14, 21, 23, 1, 11, 0, 12, 27, 7, 8, 20, 6, 25, 19, 29, 2, 4, 16, 3, 18, 26, 28]


### Brute Force


```python
def bfmax(a):
  m = a[0]
  for i in range(1, len(a)):
    if a[i] > m:
      m = a[i]
  return m
```


```python
res = bfmax(a)
assert res == 29
print(res)
```

    29


$ O(n) $

### Divide and conquer


```python
def dcmax(a, i, f):
  if i == f:
    return a[i]
  mid = (i + f) // 2
  maxleft = dcmax(a, i, mid)
  maxright = dcmax(a, mid + 1, f)
  return maxleft if maxleft > maxright else maxright
```

en c/c++

```c++
expr ? a : b
```

en python

```python
a if expre else b
```


```python
res = dcmax(a, 0, len(a) - 1)
assert res == 29
print(res)
```

    29


$$ T(n) = 2T(\frac{n}{2}) + O(1) $$

so we have:

$$
a = 2\\
b = 2\\
k = 0
$$

Then using the master theorem:

$$
T(n) = n^{\log_2{2}}\\
T(n) = n\\
T(n) \implies O(n)
$$


```python
bigboy = list(range(10000))
random.shuffle(bigboy)
%timeit bfmax(bigboy)
%timeit dcmax(bigboy, 0, 9999)
```

    1000 loops, best of 5: 769 µs per loop
    100 loops, best of 5: 4.51 ms per loop


## Sumarize list elements



```python
def _sumarize(a, i, f):
  if i == f:
    return a[i]
  else:
    mid = (i + f) // 2
    s1 = _sumarize(a, i, mid)
    s2 = _sumarize(a, mid + 1, f)
    return s1 + s2

def sumarize(a):
  return _sumarize(a, 0, len(a) - 1)
```


```python
res = sumarize(a)
assert res == sum(a)
res
```




    435



## Matrix Multiplication

for matrixes where $n = 2^k \,,\, k \in N$

### Classic way


```python
def matmul(a, b):
  n = len(a)
  c = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      accum = 0
      for k in range(n):
        accum += a[i][k] * b[k][j]
      c[i][j] = accum
  return c
```


```python
import numpy as np
```


```python
n = 8
a = np.array(list(range(n*n))).reshape((n, n))
b = np.array(list(range(n*n))).reshape((n, n))
print(a)
print(b)
```

    [[ 0  1  2  3  4  5  6  7]
     [ 8  9 10 11 12 13 14 15]
     [16 17 18 19 20 21 22 23]
     [24 25 26 27 28 29 30 31]
     [32 33 34 35 36 37 38 39]
     [40 41 42 43 44 45 46 47]
     [48 49 50 51 52 53 54 55]
     [56 57 58 59 60 61 62 63]]
    [[ 0  1  2  3  4  5  6  7]
     [ 8  9 10 11 12 13 14 15]
     [16 17 18 19 20 21 22 23]
     [24 25 26 27 28 29 30 31]
     [32 33 34 35 36 37 38 39]
     [40 41 42 43 44 45 46 47]
     [48 49 50 51 52 53 54 55]
     [56 57 58 59 60 61 62 63]]



```python
c = matmul(a, b)
np.array(c)
```




    array([[ 1120,  1148,  1176,  1204,  1232,  1260,  1288,  1316],
           [ 2912,  3004,  3096,  3188,  3280,  3372,  3464,  3556],
           [ 4704,  4860,  5016,  5172,  5328,  5484,  5640,  5796],
           [ 6496,  6716,  6936,  7156,  7376,  7596,  7816,  8036],
           [ 8288,  8572,  8856,  9140,  9424,  9708,  9992, 10276],
           [10080, 10428, 10776, 11124, 11472, 11820, 12168, 12516],
           [11872, 12284, 12696, 13108, 13520, 13932, 14344, 14756],
           [13664, 14140, 14616, 15092, 15568, 16044, 16520, 16996]])



### Divide and conquer way


```python
def dcmatmul(a, b, c, ri, rf, ci, cf):
  n = len(a)
  if ri == rf:
    accum = 0
    for k in range(n):
      accum += a[ri][k] * b[k][cf]

    c[ri][cf] = accum
  else:
    rmid = (ri + rf) // 2
    cmid = (ci + cf) // 2
    dcmatmul(a, b, c, ri, rmid, ci, cmid)
    dcmatmul(a, b, c, rmid+1, rf, ci, cmid)
    dcmatmul(a, b, c, ri, rmid, cmid +1, cf)
    dcmatmul(a, b, c, rmid+1, rf, cmid + 1, cf)
```


```python
n = 8
a = np.array(list(range(n*n))).reshape((n, n))
b = np.array(list(range(n*n))).reshape((n, n))
c = np.zeros((n, n))
dcmatmul(a, b, c, 0, n-1, 0, n-1)
print(c)
```

    [[ 1120.  1148.  1176.  1204.  1232.  1260.  1288.  1316.]
     [ 2912.  3004.  3096.  3188.  3280.  3372.  3464.  3556.]
     [ 4704.  4860.  5016.  5172.  5328.  5484.  5640.  5796.]
     [ 6496.  6716.  6936.  7156.  7376.  7596.  7816.  8036.]
     [ 8288.  8572.  8856.  9140.  9424.  9708.  9992. 10276.]
     [10080. 10428. 10776. 11124. 11472. 11820. 12168. 12516.]
     [11872. 12284. 12696. 13108. 13520. 13932. 14344. 14756.]
     [13664. 14140. 14616. 15092. 15568. 16044. 16520. 16996.]]



```python
import pdb

def dcmatmul(a, b, c, ri, rf, ci, cf):
  n = len(a)
  #pdb.set_trace()
  if ri == rf and ci == cf:
    accum = 0
    for k in range(n):
      accum += a[ri][k] * b[k][cf]

    c[ri][cf] = accum
  elif ri == rf:
    cmid = (ci + cf) // 2
    dcmatmul(a, b, c, ri, rf, ci, cmid)
    dcmatmul(a, b, c, ri, rf, cmid + 1, cf)
  elif ci == cf:
    rmid = (ri + rf) // 2
    dcmatmul(a, b, c, ri, rmid, ci, cf)
    dcmatmul(a, b, c, rmid+1, rf, ci, cf)
  else:
    rmid = (ri + rf) // 2
    cmid = (ci + cf) // 2
    dcmatmul(a, b, c, ri, rmid, ci, cmid)
    dcmatmul(a, b, c, rmid+1, rf, ci, cmid)
    dcmatmul(a, b, c, ri, rmid, cmid +1, cf)
    dcmatmul(a, b, c, rmid+1, rf, cmid + 1, cf)
```


```python
a = np.array(list(range(9))).reshape(3, 3)
b = np.array(list(range(9))).reshape(3, 3)
c = matmul(a, b)
np.array(c)
```




    array([[ 15,  18,  21],
           [ 42,  54,  66],
           [ 69,  90, 111]])




```python
c = np.zeros((3, 3))
dcmatmul(a, b, c, 0, 2, 0, 2)
c
```




    array([[ 15.,  18.,  21.],
           [ 42.,  54.,  66.],
           [  0.,  90., 111.]])




```python

```

927ca24efe4c87cbb81abd6a3874ba14b0a51858
ipynb
Jupyter Notebook
03_01_divide_and_conquer.ipynb
ronaldo91929-glic/Complejidad-Algoritmica-Curso
f690f0b4c00e7a5fd9b3316e4afd8fa7ac9bb421
CC0-1.0
2021-04-11T04:25:02.000Z
2022-03-28T22:20:58.000Z
03_01_divide_and_conquer.ipynb
ronaldo91929-glic/Complejidad-Algoritmica-Curso
f690f0b4c00e7a5fd9b3316e4afd8fa7ac9bb421
CC0-1.0
2021-10-01T22:27:37.000Z
2021-11-27T01:32:03.000Z
03_01_divide_and_conquer.ipynb
ronaldo91929-glic/Complejidad-Algoritmica-Curso
f690f0b4c00e7a5fd9b3316e4afd8fa7ac9bb421
CC0-1.0
2021-04-12T15:43:14.000Z
2022-03-15T18:07:19.000Z
Qwen/Qwen-72B
1. YES
2. YES