Divide & Conquer Tutorial

COMP202 Tutorials 2022-03-03

Running Time Alternate Method

Instead of using the method stated here we can use this easier method instead for:

\[T(n) = aT\left(\frac n b\right) + f(n)\]

where:

\[f(n) = O(n^d)\]

We can then use the following cases:

\[T(n) = \begin{cases} O(n^d) & \text{if } d>\log_ba\\ O(n^d\log_bn) &\text{if } d=log_ba\\ O(n^{log_ba}) &\text{if } d<log_ba \end{cases}\]