First step is to compare $n^{log_b a} = n^{log_4 3}= O(n^{0.793})$ with $f(n)$. I have no clue on how they compared this. The book explains:
$f(n) = Omega (n^{log_4 3+epsilon })$, where $epsilon approx 0.2$, case 3 applies if we can show that the regularity condition holds for $f(n).$
Followed by:
For sufficiently large n, we have that: $afleft(frac{n}{b}right) = 3left(frac{n}{4}right)logleft(frac{n}{5}right) leleft(frac{3}{4}right)n log n = cf(n)~ for~ c=frac{3}{4}.$
Where did $3left(frac{n}{4}right)$ come from?
Asked By : newprint
Answered By : Nicholas Mancuso
$f(n) = Omega(n^{log_b a + epsilon})$ for some $epsilon > 0$ and if $a f(n/b) leq c f(n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T(n) = Theta(f(n))$
Our recurrence is defined as $$T(n) = 3T(n/4) + n log n.$$ By definition we have, $a = 3, b = 4, f(n) = n log n$. We now need to show that $f(n)$ is polynomially larger than $n^{log_b a}$. That is the “$f(n) = Omega(n^{log_b a + epsilon})$” part from above. Defining $epsilon approx 0.2$ achieves this. The reason being that $log_4 3 approx 0.793$ and $f(n) = Omega(n^{0.793 + epsilon})$. We are left to show that $f(n)$ satisfies the regularity condition. That is the “$a f(n/b) leq c f(n)$ for some constant $c < 1$ and all sufficiently large $n$” part. We simply plug in our values of $a,b$ to get: $$a f(n/b) = 3(n/4) log (n/4).$$ All we did was take the “$n$” in $f(n)$ and plug in “$n/4$”. To make this easier to see, let $k = n/4$ and observe that $a f(k) = a k log k$. Swapping $k$ with $n/4$ we have $$3(n/4) log (n/4) leq (3/4)n log n = c f(n)$$ where $c = 3/4$. This finishes our necessary requirements and we have that $T(n) = Theta(n log n)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/3504
