According to the Master Theorem for T(n) = a T(n/b) + f(n) with a >= 1, b > 1, if f(n) = O($n^{log_b$ a-$\epsilon}$) for some constant $\epsilon > 0$, then T(n) is:
This is Case 1 of the Master Theorem. When f(n) is polynomially smaller than $n^{log_b$ a}, the solution is T(n) = $\Theta(n^{log_b a})$.
What is the solution to the recurrence relation T(n) = 2 T(n/2) + n log n?
Here $a=2, b=2, n^{log_b a} = n$. Since f(n) = n log $n = n^{log_b a} \cdot log^1 n$, by Extended Master Theorem Case 2, T(n) = $\Theta(n (log n)^{1+1}) = \Theta(n (log n)^2)$.
What is the solution to the recurrence relation T(n) = 4 T(n/2) + $n^2$ sqrt(n)?
Here $a=4, b=2, n^{log_b a} = n^2$. $f(n) = n^2$.$5 = n^{2+0$.5}. f(n) is polynomially larger than $n^2$ ($\epsilon = 0.5$) and regularity condition holds. By Case 3, T(n) = $\Theta(f(n)) = \Theta(n^2.5)$.
Solve the recurrence T(n) = T(n/2) + 1 with base case T(1) = 1.
Here $a=1, b=2, n^{log_2 1} = n^0 = 1$. f(n) = 1 = $\Theta(n^{log_b a})$. By Master Theorem Case 2 ($k=0), T(n) = \Theta(log n$).
What is the asymptotic tight bound for T(n) = 2 T(n/2) + n?
$Standard Merge Sort recurrence: a=2, b=2, n^{log_2 2} = n. f(n) = n. Master Theorem Case 2 gives T(n) = \Theta(n log n).$