Mixing
Solving T(n) = 4T(n/2) + theta(n^2 / logn)
$begingroup$
I am trying to solve
$$T(n) = 4T(n/2) + theta(n^2 / logn)$$
Edit: I know the solution is theta(n^2 log logn), i just dont know how to get there.
Any help is greatly appreciated!
Thanks!
asymptotics
asked Jan 25 at 1:48
Chris PetroneChris Petrone
11
$endgroup$
add a comment |
$begingroup$
I am trying to solve
$$T(n) = 4T(n/2) + theta(n^2 / logn)$$
Edit: I know the solution is theta(n^2 log logn), i just dont know how to get there.
Any help is greatly appreciated!
Thanks!
asymptotics
asked Jan 25 at 1:48
Chris PetroneChris Petrone
11
$endgroup$
$begingroup$
Please use MathJax
$endgroup$
– J. W. Tanner
Jan 25 at 1:55
$begingroup$
What is the function $T$?
$endgroup$
– David G. Stork
Jan 25 at 1:58
$begingroup$
you'll need some way to terminate the recursion. But given that, there's $4^k times s$, where $k$ is number of levels in the recursion, and $s$ is the number of sampling points of T-function. This pattern is the same than what happens if you try to draw blurred image by taking average of surrounding pixels of an image.
$endgroup$
– tp1
Jan 25 at 2:06
add a comment |
$begingroup$
I am trying to solve
$$T(n) = 4T(n/2) + theta(n^2 / logn)$$
Edit: I know the solution is theta(n^2 log logn), i just dont know how to get there.
Any help is greatly appreciated!
Thanks!
asymptotics
asked Jan 25 at 1:48
Chris PetroneChris Petrone
11
$endgroup$
I am trying to solve
$$T(n) = 4T(n/2) + theta(n^2 / logn)$$
Edit: I know the solution is theta(n^2 log logn), i just dont know how to get there.
Any help is greatly appreciated!
Thanks!
asymptotics
asymptotics
asked Jan 25 at 1:48
Chris PetroneChris Petrone
11
asked Jan 25 at 1:48
Chris PetroneChris Petrone
11
edited Jan 25 at 15:51
Chris Petrone
asked Jan 25 at 1:48
Chris PetroneChris Petrone
11
asked Jan 25 at 1:48
Chris PetroneChris Petrone
11
asked Jan 25 at 1:48
Chris PetroneChris Petrone
11
11
$begingroup$
Please use MathJax
$endgroup$
– J. W. Tanner
Jan 25 at 1:55
$begingroup$
What is the function $T$?
$endgroup$
– David G. Stork
Jan 25 at 1:58
$begingroup$
you'll need some way to terminate the recursion. But given that, there's $4^k times s$, where $k$ is number of levels in the recursion, and $s$ is the number of sampling points of T-function. This pattern is the same than what happens if you try to draw blurred image by taking average of surrounding pixels of an image.
$endgroup$
– tp1
Jan 25 at 2:06
add a comment |
$begingroup$
Please use MathJax
$endgroup$
– J. W. Tanner
Jan 25 at 1:55
$begingroup$
What is the function $T$?
$endgroup$
– David G. Stork
Jan 25 at 1:58
$begingroup$
you'll need some way to terminate the recursion. But given that, there's $4^k times s$, where $k$ is number of levels in the recursion, and $s$ is the number of sampling points of T-function. This pattern is the same than what happens if you try to draw blurred image by taking average of surrounding pixels of an image.
$endgroup$
– tp1
Jan 25 at 2:06
$begingroup$
Please use MathJax
$endgroup$
– J. W. Tanner
Jan 25 at 1:55
$begingroup$
Please use MathJax
$endgroup$
– J. W. Tanner
Jan 25 at 1:55
$begingroup$
What is the function $T$?
$endgroup$
– David G. Stork
Jan 25 at 1:58
$begingroup$
What is the function $T$?
$endgroup$
– David G. Stork
Jan 25 at 1:58
$begingroup$
you'll need some way to terminate the recursion. But given that, there's $4^k times s$, where $k$ is number of levels in the recursion, and $s$ is the number of sampling points of T-function. This pattern is the same than what happens if you try to draw blurred image by taking average of surrounding pixels of an image.
$endgroup$
– tp1
Jan 25 at 2:06
$begingroup$
you'll need some way to terminate the recursion. But given that, there's $4^k times s$, where $k$ is number of levels in the recursion, and $s$ is the number of sampling points of T-function. This pattern is the same than what happens if you try to draw blurred image by taking average of surrounding pixels of an image.
$endgroup$
– tp1
Jan 25 at 2:06
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
I know the solution is [T]heta(n^2 log logn), [I] just dont know how to get there.
A simple and completely self-contained way to "get there" is to consider the change of variable $$S(k)=4^{-k}T(2^k)$$ Then the recursion becomes $$S(k)=S(k-1)+Thetaleft(frac1kright)$$ from which one gets $S(k)=Theta(H_k)$ with $$H_k=sum_{ell=1}^kfrac1ellsimlog k$$ Coming back from $H_k$ to $S(k)$ and from $S(k)$ to $T(2^k)$, this yields $$T(2^k)=4^kcdotThetaleft(log kright)=Thetaleft(4^klog kright)$$ Considering that $4^k=(2^k)^2$ and that $log k=Theta(loglog 2^k)$, this rigorous result is usually extended without proof (although the implication does not hold without some supplementary regularity hypothesis) to $$T(n)=Thetaleft(n^2loglog nright)$$
answered Feb 7 at 8:13
DidDid
248k23225463
$endgroup$
add a comment |
$begingroup$
You're not supposed to prove that (even if it's true). You need to use the extended version of the Master Theorem (or you can also use the generalisation: Akra-Bazzi). You're in the case where $c = log_ba= 2$, and $f(n) = Theta(n^clog^{-1}n)$, this is a special case, it yields $T(n) = Theta(n^clog(log n))$. Refer to: https://en.m.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)
Specifically 2b.
answered Jan 25 at 2:36
lightxbulblightxbulb
1,140311
$endgroup$
$begingroup$
"You're not supposed to prove that" Well, it happens that this (a proof) is what they are asking for.
$endgroup$
– Did
Feb 7 at 8:14
$begingroup$
@Did 'That' referring to the initial loose bound he edited out after my answer. Read the original question before the edits.
$endgroup$
– lightxbulb
Feb 7 at 10:13
$begingroup$
OK, that explains things. Sorry for the noise.
$endgroup$
– Did
Feb 7 at 10:15
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%2f3086607%2fsolving-tn-4tn-2-thetan2-logn%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I know the solution is [T]heta(n^2 log logn), [I] just dont know how to get there.
A simple and completely self-contained way to "get there" is to consider the change of variable $$S(k)=4^{-k}T(2^k)$$ Then the recursion becomes $$S(k)=S(k-1)+Thetaleft(frac1kright)$$ from which one gets $S(k)=Theta(H_k)$ with $$H_k=sum_{ell=1}^kfrac1ellsimlog k$$ Coming back from $H_k$ to $S(k)$ and from $S(k)$ to $T(2^k)$, this yields $$T(2^k)=4^kcdotThetaleft(log kright)=Thetaleft(4^klog kright)$$ Considering that $4^k=(2^k)^2$ and that $log k=Theta(loglog 2^k)$, this rigorous result is usually extended without proof (although the implication does not hold without some supplementary regularity hypothesis) to $$T(n)=Thetaleft(n^2loglog nright)$$
answered Feb 7 at 8:13
DidDid
248k23225463
$endgroup$
add a comment |
$begingroup$
I know the solution is [T]heta(n^2 log logn), [I] just dont know how to get there.
A simple and completely self-contained way to "get there" is to consider the change of variable $$S(k)=4^{-k}T(2^k)$$ Then the recursion becomes $$S(k)=S(k-1)+Thetaleft(frac1kright)$$ from which one gets $S(k)=Theta(H_k)$ with $$H_k=sum_{ell=1}^kfrac1ellsimlog k$$ Coming back from $H_k$ to $S(k)$ and from $S(k)$ to $T(2^k)$, this yields $$T(2^k)=4^kcdotThetaleft(log kright)=Thetaleft(4^klog kright)$$ Considering that $4^k=(2^k)^2$ and that $log k=Theta(loglog 2^k)$, this rigorous result is usually extended without proof (although the implication does not hold without some supplementary regularity hypothesis) to $$T(n)=Thetaleft(n^2loglog nright)$$
answered Feb 7 at 8:13
DidDid
248k23225463
$endgroup$
add a comment |
$begingroup$
I know the solution is [T]heta(n^2 log logn), [I] just dont know how to get there.
A simple and completely self-contained way to "get there" is to consider the change of variable $$S(k)=4^{-k}T(2^k)$$ Then the recursion becomes $$S(k)=S(k-1)+Thetaleft(frac1kright)$$ from which one gets $S(k)=Theta(H_k)$ with $$H_k=sum_{ell=1}^kfrac1ellsimlog k$$ Coming back from $H_k$ to $S(k)$ and from $S(k)$ to $T(2^k)$, this yields $$T(2^k)=4^kcdotThetaleft(log kright)=Thetaleft(4^klog kright)$$ Considering that $4^k=(2^k)^2$ and that $log k=Theta(loglog 2^k)$, this rigorous result is usually extended without proof (although the implication does not hold without some supplementary regularity hypothesis) to $$T(n)=Thetaleft(n^2loglog nright)$$
answered Feb 7 at 8:13
DidDid
248k23225463
$endgroup$
I know the solution is [T]heta(n^2 log logn), [I] just dont know how to get there.
A simple and completely self-contained way to "get there" is to consider the change of variable $$S(k)=4^{-k}T(2^k)$$ Then the recursion becomes $$S(k)=S(k-1)+Thetaleft(frac1kright)$$ from which one gets $S(k)=Theta(H_k)$ with $$H_k=sum_{ell=1}^kfrac1ellsimlog k$$ Coming back from $H_k$ to $S(k)$ and from $S(k)$ to $T(2^k)$, this yields $$T(2^k)=4^kcdotThetaleft(log kright)=Thetaleft(4^klog kright)$$ Considering that $4^k=(2^k)^2$ and that $log k=Theta(loglog 2^k)$, this rigorous result is usually extended without proof (although the implication does not hold without some supplementary regularity hypothesis) to $$T(n)=Thetaleft(n^2loglog nright)$$
answered Feb 7 at 8:13
DidDid
248k23225463
answered Feb 7 at 8:13
DidDid
248k23225463
answered Feb 7 at 8:13
DidDid
248k23225463
answered Feb 7 at 8:13
DidDid
248k23225463
248k23225463
add a comment |
add a comment |
$begingroup$
You're not supposed to prove that (even if it's true). You need to use the extended version of the Master Theorem (or you can also use the generalisation: Akra-Bazzi). You're in the case where $c = log_ba= 2$, and $f(n) = Theta(n^clog^{-1}n)$, this is a special case, it yields $T(n) = Theta(n^clog(log n))$. Refer to: https://en.m.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)
Specifically 2b.
answered Jan 25 at 2:36
lightxbulblightxbulb
1,140311
$endgroup$
$begingroup$
"You're not supposed to prove that" Well, it happens that this (a proof) is what they are asking for.
$endgroup$
– Did
Feb 7 at 8:14
$begingroup$
@Did 'That' referring to the initial loose bound he edited out after my answer. Read the original question before the edits.
$endgroup$
– lightxbulb
Feb 7 at 10:13
$begingroup$
OK, that explains things. Sorry for the noise.
$endgroup$
– Did
Feb 7 at 10:15
add a comment |
$begingroup$
You're not supposed to prove that (even if it's true). You need to use the extended version of the Master Theorem (or you can also use the generalisation: Akra-Bazzi). You're in the case where $c = log_ba= 2$, and $f(n) = Theta(n^clog^{-1}n)$, this is a special case, it yields $T(n) = Theta(n^clog(log n))$. Refer to: https://en.m.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)
Specifically 2b.
answered Jan 25 at 2:36
lightxbulblightxbulb
1,140311
$endgroup$
$begingroup$
"You're not supposed to prove that" Well, it happens that this (a proof) is what they are asking for.
$endgroup$
– Did
Feb 7 at 8:14
$begingroup$
@Did 'That' referring to the initial loose bound he edited out after my answer. Read the original question before the edits.
$endgroup$
– lightxbulb
Feb 7 at 10:13
$begingroup$
OK, that explains things. Sorry for the noise.
$endgroup$
– Did
Feb 7 at 10:15
add a comment |
$begingroup$
You're not supposed to prove that (even if it's true). You need to use the extended version of the Master Theorem (or you can also use the generalisation: Akra-Bazzi). You're in the case where $c = log_ba= 2$, and $f(n) = Theta(n^clog^{-1}n)$, this is a special case, it yields $T(n) = Theta(n^clog(log n))$. Refer to: https://en.m.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)
Specifically 2b.
answered Jan 25 at 2:36
lightxbulblightxbulb
1,140311
$endgroup$
You're not supposed to prove that (even if it's true). You need to use the extended version of the Master Theorem (or you can also use the generalisation: Akra-Bazzi). You're in the case where $c = log_ba= 2$, and $f(n) = Theta(n^clog^{-1}n)$, this is a special case, it yields $T(n) = Theta(n^clog(log n))$. Refer to: https://en.m.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)
Specifically 2b.
answered Jan 25 at 2:36
lightxbulblightxbulb
1,140311
answered Jan 25 at 2:36
lightxbulblightxbulb
1,140311
answered Jan 25 at 2:36
lightxbulblightxbulb
1,140311
answered Jan 25 at 2:36
lightxbulblightxbulb
1,140311
1,140311
$begingroup$
"You're not supposed to prove that" Well, it happens that this (a proof) is what they are asking for.
$endgroup$
– Did
Feb 7 at 8:14
$begingroup$
@Did 'That' referring to the initial loose bound he edited out after my answer. Read the original question before the edits.
$endgroup$
– lightxbulb
Feb 7 at 10:13
$begingroup$
OK, that explains things. Sorry for the noise.
$endgroup$
– Did
Feb 7 at 10:15
add a comment |
$begingroup$
"You're not supposed to prove that" Well, it happens that this (a proof) is what they are asking for.
$endgroup$
– Did
Feb 7 at 8:14
$begingroup$
@Did 'That' referring to the initial loose bound he edited out after my answer. Read the original question before the edits.
$endgroup$
– lightxbulb
Feb 7 at 10:13
$begingroup$
OK, that explains things. Sorry for the noise.
$endgroup$
– Did
Feb 7 at 10:15
$begingroup$
"You're not supposed to prove that" Well, it happens that this (a proof) is what they are asking for.
$endgroup$
– Did
Feb 7 at 8:14
$begingroup$
"You're not supposed to prove that" Well, it happens that this (a proof) is what they are asking for.
$endgroup$
– Did
Feb 7 at 8:14
$begingroup$
@Did 'That' referring to the initial loose bound he edited out after my answer. Read the original question before the edits.
$endgroup$
– lightxbulb
Feb 7 at 10:13
$begingroup$
@Did 'That' referring to the initial loose bound he edited out after my answer. Read the original question before the edits.
$endgroup$
– lightxbulb
Feb 7 at 10:13
$begingroup$
OK, that explains things. Sorry for the noise.
$endgroup$
– Did
Feb 7 at 10:15
$begingroup$
OK, that explains things. Sorry for the noise.
$endgroup$
– Did
Feb 7 at 10:15
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%2f3086607%2fsolving-tn-4tn-2-thetan2-logn%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$
Please use MathJax
$endgroup$
– J. W. Tanner
Jan 25 at 1:55
$begingroup$
What is the function $T$?
$endgroup$
– David G. Stork
Jan 25 at 1:58
$begingroup$
you'll need some way to terminate the recursion. But given that, there's $4^k times s$, where $k$ is number of levels in the recursion, and $s$ is the number of sampling points of T-function. This pattern is the same than what happens if you try to draw blurred image by taking average of surrounding pixels of an image.
$endgroup$
– tp1
Jan 25 at 2:06