Fill-in-blank, no proofs or derivations needed!

3 Methods

  1. Substitution Method (Mathematical Induction)
  2. Recursion Tree
  3. *Master Method

1. Without T(n)

Combine dominant terms Hint: Use your calculator to find which one is larger when you’re not sure. Hint: Input $n=32$

For $n^2+nlog(n)$, $n^2\gt nlog(n)$ ⇒ $\Theta(n^2)$

image.png

log log n log n √n (log n)^2 n n^2 n^3 2^n
0.000000001 1.0 1.414214 1.0 2 4 8 4
1.584962501 3.0 2.828427 9.0 8 64 512 256
2.321928095 5.0 5.656854 25.0 32 1024 32768 4294967296
2.584962501 6.0 8.000000 36.0 64 4096 262144 0

$$ loglogn\lt logn\lt\sqrt n\lt log^2n\lt n\lt n^2\lt n^3\lt 2^n $$

2. With T(n)

Case 1: $T(n)=aT(n/b)+f(n)$ (Master Method is available)

$$ T(n)=aT(n/b)+f(n) $$

Compare $f(n)$ with $O(n^{log_ba})$ ⇒ which dominates complexity

3 cases:

  1. $f(n)=O(n^{log_ba-\epsilon})$: Merging is slower

    Or, $f(n)\lt n^{log_ba}$

  2. $f(n)=\Theta(n^{log_ba}\cdot log^kn)$:

    Or, $f(n)= n^{log_ba}\cdot log^kn$ (normally, $k=0$ thus the latter term is 1)

  3. $f(n)=\Omega(n^{log_ba+\epsilon})$: Recurrence is slower

    Or, $f(n)\gt n^{log_ba}$

where $\epsilon$ is some constant $\epsilon\gt0$

For $T(n)=2T(n/4)+\Theta(1)$,