OOG

Master Theorem

$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$ # Common Loops ```js // c is a constant greater than 1 for(int i = 1; i <= n; i = i + c) { } // O(n) for(int i = 1; i < n; i = i*2) { } // O(log n) for(int i = n; i > 0; i = i/2) { } // O(log n) for(int i = 2; i < = n; i = pow(i, c)) { } // O(log(log n)) for(int i = 0; i < n; i = i + 1) { for(int j = 0; j < n; j = j + 1) { } } // O(n^2) for(int i = 0; i < n; i = i + 1) { for(int j = i; j < n; j = j + 1) { } } // O(n^2) ``` ## Sequential Loops - Add the time complexity of the two loops - Note that the greatest growth rate loop will dominate