Would it be possible to use the master theorem to solve the following recurrence?
T(n) = 9 T(n/2) + n^3 lg n
This recurrence hasn't been mentioned before in any of the questions on StackOverflow.
Best,
2
-
1$\begingroup$ Find a recursion for H( n) = T(n)/n^3, to make things clearer. $\endgroup$– gnasher729Commented Oct 13, 2017 at 17:47
-
$\begingroup$ Use the Master Theorem $\endgroup$– theSongbirdCommented Oct 13, 2017 at 20:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
You should use the Master Theorem to solve that kind of recurrence relation:
The general form of the Master Theorem is: $T(n) = a T(n/b) + O(n^d)$ or $T(n) = a T(n/b) + f(n)$, where $f(n)$ can take multiple forms (I'll let you dive into that).
That being said, let us begin solving the recurrence relation, step by step:
$$T(n) = 9 T(n/2) + n^3 \lg n$$
Step 1: Identify a, b and d. In your relation $a = 9$, $b = 2$. We need to work a little harder to find $d$, as you can see. The function $f(n)$ is of the form $n^\mathbf{d} \log^k n$. So $f(n) = O(n^3 \lg n)$, thus $\mathbf{d} = 3$.
Step 2: Analyze the a, b, d output of your recurrence relation and decide which of the following cases is valid:
I) $a = b^d$, then $T(n) = O(n^d \log^{k+1} n)$;
II) $a < b^d$, then $T(n) = O(n^d)$;
III) $a > b^d$, then $T(n) = O(n^{\log_b a})$.
In your situation, we have $9 > 2^3$, thus $T(n) = O(n^{\log_29}) = O(n^{3.17})$.
As you can see, this is a simple exercise on asymptotic notation. Next time try to give more insight on your thoughts regarding your problems, don't just post your homework blankly.
-
$\begingroup$ You can use LaTeX to improve the typesetting of your answers. $\endgroup$ Commented Oct 13, 2017 at 22:36
-
$\begingroup$ Actually, d = 3 + eps, for every eps > 0. Fortunately $9 > 2^{3 + eps}$ for small eps. $\endgroup$ Commented Oct 14, 2017 at 0:00
-
$\begingroup$ Be aware that we have reference questions for standard exercise problems like this. You may want to check there lest you waste time and energy producing the hundredth very similar answer. $\endgroup$– RaphaelCommented Oct 14, 2017 at 10:46
-
$\begingroup$ Thanks for your help. My confusion was because I attempted to apply case 1 of master theorem without success. The problem that I was having is how to prove that n^(lg9-eps) is O(n^3 lg n). n^3 lg n is asymptotically larger, but n^(lg9-eps) is polynomially larger. Hence case 1 applies. Am I right? $\endgroup$– mhkCommented Oct 14, 2017 at 17:31