Master Theorem

Use

Used to analyse the time complexity of “divide and conquer” problems For “divide and conquer” problems:

1. the problem is repeatedly split into multiple even sub-problems, each being easier to solve
2. When the sub-problems are easy enough, they are solved
3. The results are combined to get the final result.

Overview

$T(n)=a\cdot T(n/b)+c(n)$

• $T(n)$ is the time function for input size $n$
  • e.g. $T(n)=\Theta (\log n)$
• $a$ is the number of sub-problems that the input is divided into
• $b$ is the factor with which the sub-problems’ input size decreases
• $c(n)$ is the amount of work needed to join the solved sub-problems together (cost function)
  • This is the amount of work done at each step Note: this is a recurrence relation??

Theorem

If $T(n)=aT(n/b)+\Theta (n^d)$ (where $a>0,b>1,d\ge 0$), then:

\Theta(n^d) & d \gt \log _ba\\ \Theta(n^d\log n) & d = \log _ba\\ \Theta(n^{\log _b a}) & d \lt \log _ba \end{cases}$$ Note: $\log_nn = 1$ and $\log_n 1 = 0$ # Explanation ![[Screenshot_20240926_025419_YouTube.png]] This is a visual representation of a divide and conquer algorithm From this, assuming the final division results in problems of $\Theta(1)$, can see that $T(n)$ (total work done) is: $$T(n) = c(n) + a \cdot c(n/b) + a^2 \cdot c(n/b^2) + \ldots + \Theta(n^{\log _b (a)})$$ $$= \Theta(n^{\log _b (a)}) + \sum^{\log _b (n-1)}_{i = 0} a^i \cdot c(n/b^i)$$ To compute big theta, only the biggest factor in the above expression matters, so there are 3 cases to compute $\Theta$: ## The problem gets harder (case 1) - The total amount of work at each level **increases** as the problem is divided - This is the case when $c(n) = O(n^{\log _b(a) - \epsilon})$, where $\epsilon \gt 0$ - So, the biggest factor will be the work done at the deepest level of the above tree ($n^{\log _b (a)}$) $$T(n) = \Theta(n^{\log _b (a)})$$ ## The problem stays equally hard (case 2) - The total amount of work at each level **stays the same** as the problem is divided - This is the case when $c(n) = \Theta(n^{\log _b(a)})$ - So, we have to multiply the number of levels ($\log _b (n))$) with the amount of work at a single level (we can take the deepest level, $n^{\log _b (a)}$) - For the number of levels, base of the log can be ignored, since it can be changed by multiplying by a constant, and constants are ignored for $\Theta$ $$ T(n) = \Theta(\log(n) \cdot n^{\log _b (a)})$$ ## The problem gets easier (case 3) - The total amount of work at each level **decreases** as the probelm is divided - This is the case when $c(n) = \Omega(n^{\log _b(a) + \epsilon})$, where $\epsilon \gt 0$ - So, the biggest factor will be the root node of the above tree ($c(n)$) $$T(n) = \Theta (c(n))$$ # Example Application ## Merge Sort - Merge sort process is: 1. Repeatedly divide the list into 2 equal parts 2. Once each divided list has either 1 or 2 elements, sort them 3. Merge the sorted sub-lists by comparing them element-wise - Analysis - At each step, the list is split in 2, so $a = 2$ - At each step, the list is half the original length, so $b = 2$ - To merge the lists, $2n$ comparisons are required, so $c(n) = \Theta(n)$ - Calculate - To determine which case it is, we compare work done at root level work done at any one of the levels (we take the lowest level) - Work done at root level is $c(n)$ - $c(n) = \Theta(n)$ - Work done at last level is $n^{\log _b(a)}$, since each leaf at that level is $\Theta(1)$, work done is just number of leaves at that level - $a=2, b=2$, so $n^{\log _b(a)} = n^{\log _2(2)} = n^1 = \Theta(n)$ - Since $c(n) = n^{\log _b(a)} (= \Theta(n))$, case 2 applies - $T(n) = \Theta(\log (n) \cdot n^{\log _b (a)})$ - Substitute values and simplify, $T(n) = \Theta(n \log n)$ ## Binary Search - Binary search process is: 1. Repeatedly divide the list into 2 equal parts 2. Only look at the list that contains the target element 3. Repeat until the element is found, no "combining" step is required, since once the element is found, it is immediately returned - Analysis - At each step, we are only searching in a single list (that is half the length of the original), so $a = 1$ - At each step, the list is half the original length, so $b = 2$ - There is no merging step, so $c(n) = \Theta(1)$ - Calculate - To determine which case it is, we compare work done at root level work done at any one of the levels (we take the lowest level) - Work done at root level is $c(n)$ - $c(n) = \Theta(1)$ - Work done at last level is $n^{\log _b(a)}$, since each leaf at that level is $\Theta(1)$, work done is just number of leaves at that level - $a=1, b=2$, so $n^{\log _b(a)} = n^{\log _2(1)} = n^0 = \Theta(1)$ - Since $c(n) = n^{\log _b(a)} (= \Theta(1))$, case 2 applies - $T(n) = \Theta(\log (n) \cdot n^{\log _b (a)})$ - Substitute values and simplify, $T(n) = \Theta(\log n)$