Mixing
Asymptotic bounds of $T(n) = T(n/2) + T(n/4) + T(n/8) + n$
$begingroup$
This problem is given in "Introduction to Algorithms", by Thomas H. Cormen.
I have the answer to it, but I don't understand it.
The answer is, $T(n) = Theta(n)$.
It would be really good if you can explain it using recursion tree.
recursion
asked Aug 24 '13 at 14:03
JaydeepJaydeep
113114
$endgroup$
add a comment |
$begingroup$
This problem is given in "Introduction to Algorithms", by Thomas H. Cormen.
I have the answer to it, but I don't understand it.
The answer is, $T(n) = Theta(n)$.
It would be really good if you can explain it using recursion tree.
recursion
asked Aug 24 '13 at 14:03
JaydeepJaydeep
113114
$endgroup$
$begingroup$
Has he mentioned the base case(s)?
$endgroup$
– Mohamed Ennahdi El Idrissi
Aug 1 '14 at 20:17
add a comment |
$begingroup$
This problem is given in "Introduction to Algorithms", by Thomas H. Cormen.
I have the answer to it, but I don't understand it.
The answer is, $T(n) = Theta(n)$.
It would be really good if you can explain it using recursion tree.
recursion
asked Aug 24 '13 at 14:03
JaydeepJaydeep
113114
$endgroup$
This problem is given in "Introduction to Algorithms", by Thomas H. Cormen.
I have the answer to it, but I don't understand it.
The answer is, $T(n) = Theta(n)$.
It would be really good if you can explain it using recursion tree.
recursion
recursion
asked Aug 24 '13 at 14:03
JaydeepJaydeep
113114
asked Aug 24 '13 at 14:03
JaydeepJaydeep
113114
asked Aug 24 '13 at 14:03
JaydeepJaydeep
113114
asked Aug 24 '13 at 14:03
JaydeepJaydeep
113114
asked Aug 24 '13 at 14:03
JaydeepJaydeep
113114
113114
$begingroup$
Has he mentioned the base case(s)?
$endgroup$
– Mohamed Ennahdi El Idrissi
Aug 1 '14 at 20:17
add a comment |
$begingroup$
Has he mentioned the base case(s)?
$endgroup$
– Mohamed Ennahdi El Idrissi
Aug 1 '14 at 20:17
$begingroup$
Has he mentioned the base case(s)?
$endgroup$
– Mohamed Ennahdi El Idrissi
Aug 1 '14 at 20:17
$begingroup$
Has he mentioned the base case(s)?
$endgroup$
– Mohamed Ennahdi El Idrissi
Aug 1 '14 at 20:17
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
You may be interested to know that the method at this link can be applied to your problem to produce an exact solution.
Let $$n = sum_{k=0}^{lfloor log_2 n rfloor} d_k 2^k$$ be the binary representation of $n$. Furthermore, let $T(0) = 0$ and suppose the recurrence that we are solving is in fact
$$ T(n) = T(lfloor n/2 rfloor) + T(lfloor n/4 rfloor) + T(lfloor n/8 rfloor) + n.$$
Then we have the following exact formula for $T(n)$:
$$ T(n) = sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
sum_{k=j}^{lfloor log_2 n rfloor} d_k 2^k.$$
Now let $rho_{1,2,3}$ be the inverses of the roots of
$$1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3$$
where $$rho_1 approx 0.9196433771 quad text{and} quad
rho_{2,3} approx -0.2098216888 pm 0.3031453647 i$$
so that $rho_1$ dominates.
Solving for $c_{1,2,3}$ in
$$[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3} =
c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j$$
we obtain
$$c_1 approx 0.6184199255 quad text{and} quad
c_{2,3} approx 0.1907900392 mp 0.01870058304 i.$$
To get a lower bound on $T(n)$, consider the case of a single one followed by zeros, giving
$$ T(n) ge sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
2^{lfloor log_2 n rfloor}
\ = 2^{lfloor log_2 n rfloor}
sum_{j=0}^{lfloor log_2 n rfloor} (c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j)
= 2^{lfloor log_2 n rfloor}
left(
c_1 frac{1-rho_1^{lfloor log_2 n rfloor +1}}{1-rho_1} +
c_2 frac{1-rho_2^{lfloor log_2 n rfloor +1}}{1-rho_2} +
c_3 frac{1-rho_3^{lfloor log_2 n rfloor +1}}{1-rho_3}
right).$$
This bound is actually attained.
For an upper bound, consider the case of a string of ones,
$$T(n) le sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
sum_{k=j}^{lfloor log_2 n rfloor} 2^k
\ = sum_{j=0}^{lfloor log_2 n rfloor} (c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j)
(2^{lfloor log_2 n rfloor +1} - 2^j) \ =
2^{lfloor log_2 n rfloor +1}
left(
c_1 frac{1-rho_1^{lfloor log_2 n rfloor +1}}{1-rho_1} +
c_2 frac{1-rho_2^{lfloor log_2 n rfloor +1}}{1-rho_2} +
c_3 frac{1-rho_3^{lfloor log_2 n rfloor +1}}{1-rho_3}
right) \
- left(
c_1 frac{(2rho_1)^{lfloor log_2 n rfloor +1}-1}{2rho_1-1} +
c_2 frac{1-(2rho_2)^{lfloor log_2 n rfloor +1}}{1-2rho_2} +
c_3 frac{1-(2rho_3)^{lfloor log_2 n rfloor +1}}{1-2rho_3}
right).$$
This bound too is actually attained.
To conclude we compute the asymptotics. We see that $|rho_{1,2,3}|<1$ and hence the lower bound is asymptotic to
$$ 2^{lfloor log_2 n rfloor}
left(frac{c_1}{1-rho_1} +frac{c_2}{1-rho_2} +frac{c_3}{1-rho_3} right)
= 8 times 2^{lfloor log_2 n rfloor}.$$
We also have $|2| > |2rho_1|$ and hence the upper bound is asymptotic to
$$ 2times 2^{lfloor log_2 n rfloor}
left(frac{c_1}{1-rho_1} +frac{c_2}{1-rho_2} +frac{c_3}{1-rho_3} right)
= 16 times 2^{lfloor log_2 n rfloor}.$$
It follows that
$$ T(n) in Theta
left(2^{lfloor log_2 n rfloor} right) =
Thetaleft(nright)$$
with the leading coefficient approximating the value $8$ because in the upper bound for a string of ones we have that $lfloor log_2 n rfloor$ is off by almost one from the correct value $log_2 n,$ which turns the sixteen back into eight.
edited Apr 13 '17 at 12:19
Community♦
1
answered Aug 24 '13 at 21:35
Marko RiedelMarko Riedel
40.8k340110
$endgroup$
add a comment |
$begingroup$
Here are the top two layers of the recursion tree:
All subsequent levels will have the same pattern: dividing the node of size $k$ into three pieces, of size $k/2, k/4,text{ and }k/8$. The contribution of the lecond-level nodes will be $(7/8)n$, and you can convince yourself that the contribution of the third level (which I haven't drawn) will be $7/8$ of the total contribution in the second level, namely $(7/8)^2n$. If this were to be continued forever the total contributions to $T(n)$ would be
$$
n+left(frac{7}{8}right)n+left(frac{7}{8}right)^2n+left(frac{7}{8}right)^3n+cdots
$$
so we have a geometric series and thus
$$
T(n)le frac{1}{1-frac{7}{8}} = 8n
$$
for our upper bound. In a similar way, we could count just the contribution of the leftmost branches and conclude that $T(n)ge 2n$. Putting these together gives us the desired bound, $T(n)=Theta(n)$.
answered Aug 24 '13 at 21:33
Rick DeckerRick Decker
7,63432341
$endgroup$
$begingroup$
Is the analysis for the upper bound still valid if we take into consideration the fact that $T(k) = c$ for some $k, c in mathbb{Z}_{gt 0}$? If we pretend that all leaves terminate when the leftmost branch terminates, then the work done by the leaf nodes is $3^{log_2{n}}$, which is superlinear.
$endgroup$
– void-pointer
Mar 22 '16 at 6:03
$begingroup$
what about the 'n' in the end of recurrence relation T(n)=T(n/2)+T(n/4)+T(n/8)+n ? Will the above answer if we have T(n)=T(n/2)+T(n/4)+T(n/8)+ 2^n ?
$endgroup$
– vikkyhacks
Jan 9 '17 at 14:15
add a comment |
$begingroup$
Using Akra–Bazzi method
$$a_1=a_2=a_3=1$$
$$b_1=2, b_2=4,b_3=8$$
$$f(n)=n$$
$$a_i > 0, b_i > 0$$
$$cfrac{a_1}{b_1^p}+cfrac{a_2}{b_2^p}+cfrac{a_3}{b_3^p}=1$$
$$left(cfrac{1}{2}right)^p+left(cfrac{1}{4}right)^p+left(cfrac{1}{8}right)^p=1$$
$$T(n)=Θleft(n^pleft(1+int_n^1 frac{f(x)}{x^{p+1}} , dx right)right)$$
$$int_n^1 frac{x}{x^{p+1}} , dx=n^{1-p}$$
$$implies T(n)=Θleft(n^pleft(1+ n^{1-p}right)right) = left(n^pright)*left(n^{1-p}right) = Θleft(nright)$$
Hence,
$$ T(n) = Θleft(nright) $$
a_1=a_2=a_3=1
b1=2 , b2=4 , b3=8
f(n)=n
ai>0 , bi>0
(a1/b1^p)+(a2/b2^p)+(a3/b3^p)=1
(1/2)^p+(1/4)^p+(1/8)^p=1
T(n)=Θ(n^p(1+∫n1f(x)/x^p+1dx))
∫n1x/x^p+1dx=n^1-p
T(n)=Θ(n^p(1+n^1-p)=n^p.n^1-p=Θ(n)
T(n)=Θ(n)
edited Jan 27 at 16:40
Kartikey Kumar
31
answered Jan 27 at 12:08
N.HashemiN.Hashemi
112
$endgroup$
$begingroup$
here is a mathjax guide to type maths on this site.
$endgroup$
– Siong Thye Goh
Jan 27 at 12:31
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f475090%2fasymptotic-bounds-of-tn-tn-2-tn-4-tn-8-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You may be interested to know that the method at this link can be applied to your problem to produce an exact solution.
Let $$n = sum_{k=0}^{lfloor log_2 n rfloor} d_k 2^k$$ be the binary representation of $n$. Furthermore, let $T(0) = 0$ and suppose the recurrence that we are solving is in fact
$$ T(n) = T(lfloor n/2 rfloor) + T(lfloor n/4 rfloor) + T(lfloor n/8 rfloor) + n.$$
Then we have the following exact formula for $T(n)$:
$$ T(n) = sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
sum_{k=j}^{lfloor log_2 n rfloor} d_k 2^k.$$
Now let $rho_{1,2,3}$ be the inverses of the roots of
$$1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3$$
where $$rho_1 approx 0.9196433771 quad text{and} quad
rho_{2,3} approx -0.2098216888 pm 0.3031453647 i$$
so that $rho_1$ dominates.
Solving for $c_{1,2,3}$ in
$$[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3} =
c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j$$
we obtain
$$c_1 approx 0.6184199255 quad text{and} quad
c_{2,3} approx 0.1907900392 mp 0.01870058304 i.$$
To get a lower bound on $T(n)$, consider the case of a single one followed by zeros, giving
$$ T(n) ge sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
2^{lfloor log_2 n rfloor}
\ = 2^{lfloor log_2 n rfloor}
sum_{j=0}^{lfloor log_2 n rfloor} (c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j)
= 2^{lfloor log_2 n rfloor}
left(
c_1 frac{1-rho_1^{lfloor log_2 n rfloor +1}}{1-rho_1} +
c_2 frac{1-rho_2^{lfloor log_2 n rfloor +1}}{1-rho_2} +
c_3 frac{1-rho_3^{lfloor log_2 n rfloor +1}}{1-rho_3}
right).$$
This bound is actually attained.
For an upper bound, consider the case of a string of ones,
$$T(n) le sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
sum_{k=j}^{lfloor log_2 n rfloor} 2^k
\ = sum_{j=0}^{lfloor log_2 n rfloor} (c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j)
(2^{lfloor log_2 n rfloor +1} - 2^j) \ =
2^{lfloor log_2 n rfloor +1}
left(
c_1 frac{1-rho_1^{lfloor log_2 n rfloor +1}}{1-rho_1} +
c_2 frac{1-rho_2^{lfloor log_2 n rfloor +1}}{1-rho_2} +
c_3 frac{1-rho_3^{lfloor log_2 n rfloor +1}}{1-rho_3}
right) \
- left(
c_1 frac{(2rho_1)^{lfloor log_2 n rfloor +1}-1}{2rho_1-1} +
c_2 frac{1-(2rho_2)^{lfloor log_2 n rfloor +1}}{1-2rho_2} +
c_3 frac{1-(2rho_3)^{lfloor log_2 n rfloor +1}}{1-2rho_3}
right).$$
This bound too is actually attained.
To conclude we compute the asymptotics. We see that $|rho_{1,2,3}|<1$ and hence the lower bound is asymptotic to
$$ 2^{lfloor log_2 n rfloor}
left(frac{c_1}{1-rho_1} +frac{c_2}{1-rho_2} +frac{c_3}{1-rho_3} right)
= 8 times 2^{lfloor log_2 n rfloor}.$$
We also have $|2| > |2rho_1|$ and hence the upper bound is asymptotic to
$$ 2times 2^{lfloor log_2 n rfloor}
left(frac{c_1}{1-rho_1} +frac{c_2}{1-rho_2} +frac{c_3}{1-rho_3} right)
= 16 times 2^{lfloor log_2 n rfloor}.$$
It follows that
$$ T(n) in Theta
left(2^{lfloor log_2 n rfloor} right) =
Thetaleft(nright)$$
with the leading coefficient approximating the value $8$ because in the upper bound for a string of ones we have that $lfloor log_2 n rfloor$ is off by almost one from the correct value $log_2 n,$ which turns the sixteen back into eight.
edited Apr 13 '17 at 12:19
Community♦
1
answered Aug 24 '13 at 21:35
Marko RiedelMarko Riedel
40.8k340110
$endgroup$
add a comment |
$begingroup$
You may be interested to know that the method at this link can be applied to your problem to produce an exact solution.
Let $$n = sum_{k=0}^{lfloor log_2 n rfloor} d_k 2^k$$ be the binary representation of $n$. Furthermore, let $T(0) = 0$ and suppose the recurrence that we are solving is in fact
$$ T(n) = T(lfloor n/2 rfloor) + T(lfloor n/4 rfloor) + T(lfloor n/8 rfloor) + n.$$
Then we have the following exact formula for $T(n)$:
$$ T(n) = sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
sum_{k=j}^{lfloor log_2 n rfloor} d_k 2^k.$$
Now let $rho_{1,2,3}$ be the inverses of the roots of
$$1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3$$
where $$rho_1 approx 0.9196433771 quad text{and} quad
rho_{2,3} approx -0.2098216888 pm 0.3031453647 i$$
so that $rho_1$ dominates.
Solving for $c_{1,2,3}$ in
$$[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3} =
c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j$$
we obtain
$$c_1 approx 0.6184199255 quad text{and} quad
c_{2,3} approx 0.1907900392 mp 0.01870058304 i.$$
To get a lower bound on $T(n)$, consider the case of a single one followed by zeros, giving
$$ T(n) ge sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
2^{lfloor log_2 n rfloor}
\ = 2^{lfloor log_2 n rfloor}
sum_{j=0}^{lfloor log_2 n rfloor} (c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j)
= 2^{lfloor log_2 n rfloor}
left(
c_1 frac{1-rho_1^{lfloor log_2 n rfloor +1}}{1-rho_1} +
c_2 frac{1-rho_2^{lfloor log_2 n rfloor +1}}{1-rho_2} +
c_3 frac{1-rho_3^{lfloor log_2 n rfloor +1}}{1-rho_3}
right).$$
This bound is actually attained.
For an upper bound, consider the case of a string of ones,
$$T(n) le sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
sum_{k=j}^{lfloor log_2 n rfloor} 2^k
\ = sum_{j=0}^{lfloor log_2 n rfloor} (c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j)
(2^{lfloor log_2 n rfloor +1} - 2^j) \ =
2^{lfloor log_2 n rfloor +1}
left(
c_1 frac{1-rho_1^{lfloor log_2 n rfloor +1}}{1-rho_1} +
c_2 frac{1-rho_2^{lfloor log_2 n rfloor +1}}{1-rho_2} +
c_3 frac{1-rho_3^{lfloor log_2 n rfloor +1}}{1-rho_3}
right) \
- left(
c_1 frac{(2rho_1)^{lfloor log_2 n rfloor +1}-1}{2rho_1-1} +
c_2 frac{1-(2rho_2)^{lfloor log_2 n rfloor +1}}{1-2rho_2} +
c_3 frac{1-(2rho_3)^{lfloor log_2 n rfloor +1}}{1-2rho_3}
right).$$
This bound too is actually attained.
To conclude we compute the asymptotics. We see that $|rho_{1,2,3}|<1$ and hence the lower bound is asymptotic to
$$ 2^{lfloor log_2 n rfloor}
left(frac{c_1}{1-rho_1} +frac{c_2}{1-rho_2} +frac{c_3}{1-rho_3} right)
= 8 times 2^{lfloor log_2 n rfloor}.$$
We also have $|2| > |2rho_1|$ and hence the upper bound is asymptotic to
$$ 2times 2^{lfloor log_2 n rfloor}
left(frac{c_1}{1-rho_1} +frac{c_2}{1-rho_2} +frac{c_3}{1-rho_3} right)
= 16 times 2^{lfloor log_2 n rfloor}.$$
It follows that
$$ T(n) in Theta
left(2^{lfloor log_2 n rfloor} right) =
Thetaleft(nright)$$
with the leading coefficient approximating the value $8$ because in the upper bound for a string of ones we have that $lfloor log_2 n rfloor$ is off by almost one from the correct value $log_2 n,$ which turns the sixteen back into eight.
edited Apr 13 '17 at 12:19
Community♦
1
answered Aug 24 '13 at 21:35
Marko RiedelMarko Riedel
40.8k340110
$endgroup$
add a comment |
$begingroup$
You may be interested to know that the method at this link can be applied to your problem to produce an exact solution.
Let $$n = sum_{k=0}^{lfloor log_2 n rfloor} d_k 2^k$$ be the binary representation of $n$. Furthermore, let $T(0) = 0$ and suppose the recurrence that we are solving is in fact
$$ T(n) = T(lfloor n/2 rfloor) + T(lfloor n/4 rfloor) + T(lfloor n/8 rfloor) + n.$$
Then we have the following exact formula for $T(n)$:
$$ T(n) = sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
sum_{k=j}^{lfloor log_2 n rfloor} d_k 2^k.$$
Now let $rho_{1,2,3}$ be the inverses of the roots of
$$1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3$$
where $$rho_1 approx 0.9196433771 quad text{and} quad
rho_{2,3} approx -0.2098216888 pm 0.3031453647 i$$
so that $rho_1$ dominates.
Solving for $c_{1,2,3}$ in
$$[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3} =
c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j$$
we obtain
$$c_1 approx 0.6184199255 quad text{and} quad
c_{2,3} approx 0.1907900392 mp 0.01870058304 i.$$
To get a lower bound on $T(n)$, consider the case of a single one followed by zeros, giving
$$ T(n) ge sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
2^{lfloor log_2 n rfloor}
\ = 2^{lfloor log_2 n rfloor}
sum_{j=0}^{lfloor log_2 n rfloor} (c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j)
= 2^{lfloor log_2 n rfloor}
left(
c_1 frac{1-rho_1^{lfloor log_2 n rfloor +1}}{1-rho_1} +
c_2 frac{1-rho_2^{lfloor log_2 n rfloor +1}}{1-rho_2} +
c_3 frac{1-rho_3^{lfloor log_2 n rfloor +1}}{1-rho_3}
right).$$
This bound is actually attained.
For an upper bound, consider the case of a string of ones,
$$T(n) le sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
sum_{k=j}^{lfloor log_2 n rfloor} 2^k
\ = sum_{j=0}^{lfloor log_2 n rfloor} (c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j)
(2^{lfloor log_2 n rfloor +1} - 2^j) \ =
2^{lfloor log_2 n rfloor +1}
left(
c_1 frac{1-rho_1^{lfloor log_2 n rfloor +1}}{1-rho_1} +
c_2 frac{1-rho_2^{lfloor log_2 n rfloor +1}}{1-rho_2} +
c_3 frac{1-rho_3^{lfloor log_2 n rfloor +1}}{1-rho_3}
right) \
- left(
c_1 frac{(2rho_1)^{lfloor log_2 n rfloor +1}-1}{2rho_1-1} +
c_2 frac{1-(2rho_2)^{lfloor log_2 n rfloor +1}}{1-2rho_2} +
c_3 frac{1-(2rho_3)^{lfloor log_2 n rfloor +1}}{1-2rho_3}
right).$$
This bound too is actually attained.
To conclude we compute the asymptotics. We see that $|rho_{1,2,3}|<1$ and hence the lower bound is asymptotic to
$$ 2^{lfloor log_2 n rfloor}
left(frac{c_1}{1-rho_1} +frac{c_2}{1-rho_2} +frac{c_3}{1-rho_3} right)
= 8 times 2^{lfloor log_2 n rfloor}.$$
We also have $|2| > |2rho_1|$ and hence the upper bound is asymptotic to
$$ 2times 2^{lfloor log_2 n rfloor}
left(frac{c_1}{1-rho_1} +frac{c_2}{1-rho_2} +frac{c_3}{1-rho_3} right)
= 16 times 2^{lfloor log_2 n rfloor}.$$
It follows that
$$ T(n) in Theta
left(2^{lfloor log_2 n rfloor} right) =
Thetaleft(nright)$$
with the leading coefficient approximating the value $8$ because in the upper bound for a string of ones we have that $lfloor log_2 n rfloor$ is off by almost one from the correct value $log_2 n,$ which turns the sixteen back into eight.
edited Apr 13 '17 at 12:19
Community♦
1
answered Aug 24 '13 at 21:35
Marko RiedelMarko Riedel
40.8k340110
$endgroup$
You may be interested to know that the method at this link can be applied to your problem to produce an exact solution.
Let $$n = sum_{k=0}^{lfloor log_2 n rfloor} d_k 2^k$$ be the binary representation of $n$. Furthermore, let $T(0) = 0$ and suppose the recurrence that we are solving is in fact
$$ T(n) = T(lfloor n/2 rfloor) + T(lfloor n/4 rfloor) + T(lfloor n/8 rfloor) + n.$$
Then we have the following exact formula for $T(n)$:
$$ T(n) = sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
sum_{k=j}^{lfloor log_2 n rfloor} d_k 2^k.$$
Now let $rho_{1,2,3}$ be the inverses of the roots of
$$1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3$$
where $$rho_1 approx 0.9196433771 quad text{and} quad
rho_{2,3} approx -0.2098216888 pm 0.3031453647 i$$
so that $rho_1$ dominates.
Solving for $c_{1,2,3}$ in
$$[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3} =
c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j$$
we obtain
$$c_1 approx 0.6184199255 quad text{and} quad
c_{2,3} approx 0.1907900392 mp 0.01870058304 i.$$
To get a lower bound on $T(n)$, consider the case of a single one followed by zeros, giving
$$ T(n) ge sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
2^{lfloor log_2 n rfloor}
\ = 2^{lfloor log_2 n rfloor}
sum_{j=0}^{lfloor log_2 n rfloor} (c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j)
= 2^{lfloor log_2 n rfloor}
left(
c_1 frac{1-rho_1^{lfloor log_2 n rfloor +1}}{1-rho_1} +
c_2 frac{1-rho_2^{lfloor log_2 n rfloor +1}}{1-rho_2} +
c_3 frac{1-rho_3^{lfloor log_2 n rfloor +1}}{1-rho_3}
right).$$
This bound is actually attained.
For an upper bound, consider the case of a string of ones,
$$T(n) le sum_{j=0}^{lfloor log_2 n rfloor}
[z^j] frac{1}{1 - frac{1}{2} z - frac{1}{4} z^2 - frac{1}{8} z^3}
sum_{k=j}^{lfloor log_2 n rfloor} 2^k
\ = sum_{j=0}^{lfloor log_2 n rfloor} (c_1 rho_1^j + c_2 rho_2^j + c_3 rho_3^j)
(2^{lfloor log_2 n rfloor +1} - 2^j) \ =
2^{lfloor log_2 n rfloor +1}
left(
c_1 frac{1-rho_1^{lfloor log_2 n rfloor +1}}{1-rho_1} +
c_2 frac{1-rho_2^{lfloor log_2 n rfloor +1}}{1-rho_2} +
c_3 frac{1-rho_3^{lfloor log_2 n rfloor +1}}{1-rho_3}
right) \
- left(
c_1 frac{(2rho_1)^{lfloor log_2 n rfloor +1}-1}{2rho_1-1} +
c_2 frac{1-(2rho_2)^{lfloor log_2 n rfloor +1}}{1-2rho_2} +
c_3 frac{1-(2rho_3)^{lfloor log_2 n rfloor +1}}{1-2rho_3}
right).$$
This bound too is actually attained.
To conclude we compute the asymptotics. We see that $|rho_{1,2,3}|<1$ and hence the lower bound is asymptotic to
$$ 2^{lfloor log_2 n rfloor}
left(frac{c_1}{1-rho_1} +frac{c_2}{1-rho_2} +frac{c_3}{1-rho_3} right)
= 8 times 2^{lfloor log_2 n rfloor}.$$
We also have $|2| > |2rho_1|$ and hence the upper bound is asymptotic to
$$ 2times 2^{lfloor log_2 n rfloor}
left(frac{c_1}{1-rho_1} +frac{c_2}{1-rho_2} +frac{c_3}{1-rho_3} right)
= 16 times 2^{lfloor log_2 n rfloor}.$$
It follows that
$$ T(n) in Theta
left(2^{lfloor log_2 n rfloor} right) =
Thetaleft(nright)$$
with the leading coefficient approximating the value $8$ because in the upper bound for a string of ones we have that $lfloor log_2 n rfloor$ is off by almost one from the correct value $log_2 n,$ which turns the sixteen back into eight.
edited Apr 13 '17 at 12:19
Community♦
1
answered Aug 24 '13 at 21:35
Marko RiedelMarko Riedel
40.8k340110
edited Apr 13 '17 at 12:19
Community♦
1
edited Apr 13 '17 at 12:19
Community♦
1
edited Apr 13 '17 at 12:19
Community♦
1
1
answered Aug 24 '13 at 21:35
Marko RiedelMarko Riedel
40.8k340110
answered Aug 24 '13 at 21:35
Marko RiedelMarko Riedel
40.8k340110
answered Aug 24 '13 at 21:35
Marko RiedelMarko Riedel
40.8k340110
40.8k340110
add a comment |
add a comment |
$begingroup$
Here are the top two layers of the recursion tree:
All subsequent levels will have the same pattern: dividing the node of size $k$ into three pieces, of size $k/2, k/4,text{ and }k/8$. The contribution of the lecond-level nodes will be $(7/8)n$, and you can convince yourself that the contribution of the third level (which I haven't drawn) will be $7/8$ of the total contribution in the second level, namely $(7/8)^2n$. If this were to be continued forever the total contributions to $T(n)$ would be
$$
n+left(frac{7}{8}right)n+left(frac{7}{8}right)^2n+left(frac{7}{8}right)^3n+cdots
$$
so we have a geometric series and thus
$$
T(n)le frac{1}{1-frac{7}{8}} = 8n
$$
for our upper bound. In a similar way, we could count just the contribution of the leftmost branches and conclude that $T(n)ge 2n$. Putting these together gives us the desired bound, $T(n)=Theta(n)$.
answered Aug 24 '13 at 21:33
Rick DeckerRick Decker
7,63432341
$endgroup$
$begingroup$
Is the analysis for the upper bound still valid if we take into consideration the fact that $T(k) = c$ for some $k, c in mathbb{Z}_{gt 0}$? If we pretend that all leaves terminate when the leftmost branch terminates, then the work done by the leaf nodes is $3^{log_2{n}}$, which is superlinear.
$endgroup$
– void-pointer
Mar 22 '16 at 6:03
$begingroup$
what about the 'n' in the end of recurrence relation T(n)=T(n/2)+T(n/4)+T(n/8)+n ? Will the above answer if we have T(n)=T(n/2)+T(n/4)+T(n/8)+ 2^n ?
$endgroup$
– vikkyhacks
Jan 9 '17 at 14:15
add a comment |
$begingroup$
Here are the top two layers of the recursion tree:
All subsequent levels will have the same pattern: dividing the node of size $k$ into three pieces, of size $k/2, k/4,text{ and }k/8$. The contribution of the lecond-level nodes will be $(7/8)n$, and you can convince yourself that the contribution of the third level (which I haven't drawn) will be $7/8$ of the total contribution in the second level, namely $(7/8)^2n$. If this were to be continued forever the total contributions to $T(n)$ would be
$$
n+left(frac{7}{8}right)n+left(frac{7}{8}right)^2n+left(frac{7}{8}right)^3n+cdots
$$
so we have a geometric series and thus
$$
T(n)le frac{1}{1-frac{7}{8}} = 8n
$$
for our upper bound. In a similar way, we could count just the contribution of the leftmost branches and conclude that $T(n)ge 2n$. Putting these together gives us the desired bound, $T(n)=Theta(n)$.
answered Aug 24 '13 at 21:33
Rick DeckerRick Decker
7,63432341
$endgroup$
$begingroup$
Is the analysis for the upper bound still valid if we take into consideration the fact that $T(k) = c$ for some $k, c in mathbb{Z}_{gt 0}$? If we pretend that all leaves terminate when the leftmost branch terminates, then the work done by the leaf nodes is $3^{log_2{n}}$, which is superlinear.
$endgroup$
– void-pointer
Mar 22 '16 at 6:03
$begingroup$
what about the 'n' in the end of recurrence relation T(n)=T(n/2)+T(n/4)+T(n/8)+n ? Will the above answer if we have T(n)=T(n/2)+T(n/4)+T(n/8)+ 2^n ?
$endgroup$
– vikkyhacks
Jan 9 '17 at 14:15
add a comment |
$begingroup$
Here are the top two layers of the recursion tree:
All subsequent levels will have the same pattern: dividing the node of size $k$ into three pieces, of size $k/2, k/4,text{ and }k/8$. The contribution of the lecond-level nodes will be $(7/8)n$, and you can convince yourself that the contribution of the third level (which I haven't drawn) will be $7/8$ of the total contribution in the second level, namely $(7/8)^2n$. If this were to be continued forever the total contributions to $T(n)$ would be
$$
n+left(frac{7}{8}right)n+left(frac{7}{8}right)^2n+left(frac{7}{8}right)^3n+cdots
$$
so we have a geometric series and thus
$$
T(n)le frac{1}{1-frac{7}{8}} = 8n
$$
for our upper bound. In a similar way, we could count just the contribution of the leftmost branches and conclude that $T(n)ge 2n$. Putting these together gives us the desired bound, $T(n)=Theta(n)$.
answered Aug 24 '13 at 21:33
Rick DeckerRick Decker
7,63432341
$endgroup$
Here are the top two layers of the recursion tree:
All subsequent levels will have the same pattern: dividing the node of size $k$ into three pieces, of size $k/2, k/4,text{ and }k/8$. The contribution of the lecond-level nodes will be $(7/8)n$, and you can convince yourself that the contribution of the third level (which I haven't drawn) will be $7/8$ of the total contribution in the second level, namely $(7/8)^2n$. If this were to be continued forever the total contributions to $T(n)$ would be
$$
n+left(frac{7}{8}right)n+left(frac{7}{8}right)^2n+left(frac{7}{8}right)^3n+cdots
$$
so we have a geometric series and thus
$$
T(n)le frac{1}{1-frac{7}{8}} = 8n
$$
for our upper bound. In a similar way, we could count just the contribution of the leftmost branches and conclude that $T(n)ge 2n$. Putting these together gives us the desired bound, $T(n)=Theta(n)$.
answered Aug 24 '13 at 21:33
Rick DeckerRick Decker
7,63432341
answered Aug 24 '13 at 21:33
Rick DeckerRick Decker
7,63432341
answered Aug 24 '13 at 21:33
Rick DeckerRick Decker
7,63432341
answered Aug 24 '13 at 21:33
Rick DeckerRick Decker
7,63432341
7,63432341
$begingroup$
Is the analysis for the upper bound still valid if we take into consideration the fact that $T(k) = c$ for some $k, c in mathbb{Z}_{gt 0}$? If we pretend that all leaves terminate when the leftmost branch terminates, then the work done by the leaf nodes is $3^{log_2{n}}$, which is superlinear.
$endgroup$
– void-pointer
Mar 22 '16 at 6:03
$begingroup$
what about the 'n' in the end of recurrence relation T(n)=T(n/2)+T(n/4)+T(n/8)+n ? Will the above answer if we have T(n)=T(n/2)+T(n/4)+T(n/8)+ 2^n ?
$endgroup$
– vikkyhacks
Jan 9 '17 at 14:15
add a comment |
$begingroup$
Is the analysis for the upper bound still valid if we take into consideration the fact that $T(k) = c$ for some $k, c in mathbb{Z}_{gt 0}$? If we pretend that all leaves terminate when the leftmost branch terminates, then the work done by the leaf nodes is $3^{log_2{n}}$, which is superlinear.
$endgroup$
– void-pointer
Mar 22 '16 at 6:03
$begingroup$
what about the 'n' in the end of recurrence relation T(n)=T(n/2)+T(n/4)+T(n/8)+n ? Will the above answer if we have T(n)=T(n/2)+T(n/4)+T(n/8)+ 2^n ?
$endgroup$
– vikkyhacks
Jan 9 '17 at 14:15
$begingroup$
Is the analysis for the upper bound still valid if we take into consideration the fact that $T(k) = c$ for some $k, c in mathbb{Z}_{gt 0}$? If we pretend that all leaves terminate when the leftmost branch terminates, then the work done by the leaf nodes is $3^{log_2{n}}$, which is superlinear.
$endgroup$
– void-pointer
Mar 22 '16 at 6:03
$begingroup$
Is the analysis for the upper bound still valid if we take into consideration the fact that $T(k) = c$ for some $k, c in mathbb{Z}_{gt 0}$? If we pretend that all leaves terminate when the leftmost branch terminates, then the work done by the leaf nodes is $3^{log_2{n}}$, which is superlinear.
$endgroup$
– void-pointer
Mar 22 '16 at 6:03
$begingroup$
what about the 'n' in the end of recurrence relation T(n)=T(n/2)+T(n/4)+T(n/8)+n ? Will the above answer if we have T(n)=T(n/2)+T(n/4)+T(n/8)+ 2^n ?
$endgroup$
– vikkyhacks
Jan 9 '17 at 14:15
$begingroup$
what about the 'n' in the end of recurrence relation T(n)=T(n/2)+T(n/4)+T(n/8)+n ? Will the above answer if we have T(n)=T(n/2)+T(n/4)+T(n/8)+ 2^n ?
$endgroup$
– vikkyhacks
Jan 9 '17 at 14:15
add a comment |
$begingroup$
Using Akra–Bazzi method
$$a_1=a_2=a_3=1$$
$$b_1=2, b_2=4,b_3=8$$
$$f(n)=n$$
$$a_i > 0, b_i > 0$$
$$cfrac{a_1}{b_1^p}+cfrac{a_2}{b_2^p}+cfrac{a_3}{b_3^p}=1$$
$$left(cfrac{1}{2}right)^p+left(cfrac{1}{4}right)^p+left(cfrac{1}{8}right)^p=1$$
$$T(n)=Θleft(n^pleft(1+int_n^1 frac{f(x)}{x^{p+1}} , dx right)right)$$
$$int_n^1 frac{x}{x^{p+1}} , dx=n^{1-p}$$
$$implies T(n)=Θleft(n^pleft(1+ n^{1-p}right)right) = left(n^pright)*left(n^{1-p}right) = Θleft(nright)$$
Hence,
$$ T(n) = Θleft(nright) $$
a_1=a_2=a_3=1
b1=2 , b2=4 , b3=8
f(n)=n
ai>0 , bi>0
(a1/b1^p)+(a2/b2^p)+(a3/b3^p)=1
(1/2)^p+(1/4)^p+(1/8)^p=1
T(n)=Θ(n^p(1+∫n1f(x)/x^p+1dx))
∫n1x/x^p+1dx=n^1-p
T(n)=Θ(n^p(1+n^1-p)=n^p.n^1-p=Θ(n)
T(n)=Θ(n)
edited Jan 27 at 16:40
Kartikey Kumar
31
answered Jan 27 at 12:08
N.HashemiN.Hashemi
112
$endgroup$
$begingroup$
here is a mathjax guide to type maths on this site.
$endgroup$
– Siong Thye Goh
Jan 27 at 12:31
add a comment |
$begingroup$
Using Akra–Bazzi method
$$a_1=a_2=a_3=1$$
$$b_1=2, b_2=4,b_3=8$$
$$f(n)=n$$
$$a_i > 0, b_i > 0$$
$$cfrac{a_1}{b_1^p}+cfrac{a_2}{b_2^p}+cfrac{a_3}{b_3^p}=1$$
$$left(cfrac{1}{2}right)^p+left(cfrac{1}{4}right)^p+left(cfrac{1}{8}right)^p=1$$
$$T(n)=Θleft(n^pleft(1+int_n^1 frac{f(x)}{x^{p+1}} , dx right)right)$$
$$int_n^1 frac{x}{x^{p+1}} , dx=n^{1-p}$$
$$implies T(n)=Θleft(n^pleft(1+ n^{1-p}right)right) = left(n^pright)*left(n^{1-p}right) = Θleft(nright)$$
Hence,
$$ T(n) = Θleft(nright) $$
a_1=a_2=a_3=1
b1=2 , b2=4 , b3=8
f(n)=n
ai>0 , bi>0
(a1/b1^p)+(a2/b2^p)+(a3/b3^p)=1
(1/2)^p+(1/4)^p+(1/8)^p=1
T(n)=Θ(n^p(1+∫n1f(x)/x^p+1dx))
∫n1x/x^p+1dx=n^1-p
T(n)=Θ(n^p(1+n^1-p)=n^p.n^1-p=Θ(n)
T(n)=Θ(n)
edited Jan 27 at 16:40
Kartikey Kumar
31
answered Jan 27 at 12:08
N.HashemiN.Hashemi
112
$endgroup$
$begingroup$
here is a mathjax guide to type maths on this site.
$endgroup$
– Siong Thye Goh
Jan 27 at 12:31
add a comment |
$begingroup$
Using Akra–Bazzi method
$$a_1=a_2=a_3=1$$
$$b_1=2, b_2=4,b_3=8$$
$$f(n)=n$$
$$a_i > 0, b_i > 0$$
$$cfrac{a_1}{b_1^p}+cfrac{a_2}{b_2^p}+cfrac{a_3}{b_3^p}=1$$
$$left(cfrac{1}{2}right)^p+left(cfrac{1}{4}right)^p+left(cfrac{1}{8}right)^p=1$$
$$T(n)=Θleft(n^pleft(1+int_n^1 frac{f(x)}{x^{p+1}} , dx right)right)$$
$$int_n^1 frac{x}{x^{p+1}} , dx=n^{1-p}$$
$$implies T(n)=Θleft(n^pleft(1+ n^{1-p}right)right) = left(n^pright)*left(n^{1-p}right) = Θleft(nright)$$
Hence,
$$ T(n) = Θleft(nright) $$
a_1=a_2=a_3=1
b1=2 , b2=4 , b3=8
f(n)=n
ai>0 , bi>0
(a1/b1^p)+(a2/b2^p)+(a3/b3^p)=1
(1/2)^p+(1/4)^p+(1/8)^p=1
T(n)=Θ(n^p(1+∫n1f(x)/x^p+1dx))
∫n1x/x^p+1dx=n^1-p
T(n)=Θ(n^p(1+n^1-p)=n^p.n^1-p=Θ(n)
T(n)=Θ(n)
edited Jan 27 at 16:40
Kartikey Kumar
31
answered Jan 27 at 12:08
N.HashemiN.Hashemi
112
$endgroup$
Using Akra–Bazzi method
$$a_1=a_2=a_3=1$$
$$b_1=2, b_2=4,b_3=8$$
$$f(n)=n$$
$$a_i > 0, b_i > 0$$
$$cfrac{a_1}{b_1^p}+cfrac{a_2}{b_2^p}+cfrac{a_3}{b_3^p}=1$$
$$left(cfrac{1}{2}right)^p+left(cfrac{1}{4}right)^p+left(cfrac{1}{8}right)^p=1$$
$$T(n)=Θleft(n^pleft(1+int_n^1 frac{f(x)}{x^{p+1}} , dx right)right)$$
$$int_n^1 frac{x}{x^{p+1}} , dx=n^{1-p}$$
$$implies T(n)=Θleft(n^pleft(1+ n^{1-p}right)right) = left(n^pright)*left(n^{1-p}right) = Θleft(nright)$$
Hence,
$$ T(n) = Θleft(nright) $$
a_1=a_2=a_3=1
b1=2 , b2=4 , b3=8
f(n)=n
ai>0 , bi>0
(a1/b1^p)+(a2/b2^p)+(a3/b3^p)=1
(1/2)^p+(1/4)^p+(1/8)^p=1
T(n)=Θ(n^p(1+∫n1f(x)/x^p+1dx))
∫n1x/x^p+1dx=n^1-p
T(n)=Θ(n^p(1+n^1-p)=n^p.n^1-p=Θ(n)
T(n)=Θ(n)
edited Jan 27 at 16:40
Kartikey Kumar
31
answered Jan 27 at 12:08
N.HashemiN.Hashemi
112
edited Jan 27 at 16:40
Kartikey Kumar
31
edited Jan 27 at 16:40
Kartikey Kumar
31
edited Jan 27 at 16:40
Kartikey Kumar
31
31
answered Jan 27 at 12:08
N.HashemiN.Hashemi
112
answered Jan 27 at 12:08
N.HashemiN.Hashemi
112
answered Jan 27 at 12:08
N.HashemiN.Hashemi
112
112
$begingroup$
here is a mathjax guide to type maths on this site.
$endgroup$
– Siong Thye Goh
Jan 27 at 12:31
add a comment |
$begingroup$
here is a mathjax guide to type maths on this site.
$endgroup$
– Siong Thye Goh
Jan 27 at 12:31
$begingroup$
here is a mathjax guide to type maths on this site.
$endgroup$
– Siong Thye Goh
Jan 27 at 12:31
$begingroup$
here is a mathjax guide to type maths on this site.
$endgroup$
– Siong Thye Goh
Jan 27 at 12:31
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f475090%2fasymptotic-bounds-of-tn-tn-2-tn-4-tn-8-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Has he mentioned the base case(s)?
$endgroup$
– Mohamed Ennahdi El Idrissi
Aug 1 '14 at 20:17