Mixing
Solving the recurrence $T(n) = 3Tleft(frac{n}{3}right) + nlog_2 n$
$begingroup$
I've seen plenty of discussion regarding solving recurrences like this with the master theorem, but I need to solve it via back substitution. Was doing pretty good until I got stuck in the summation part.
Assumptions are that $n$ is a power of $3$ so $n = 3^k$ and hence $k = log_3(n)$. Also $T(1) = 1$.
After substituting $3$ functions to recognize the pattern I found this general form for the recurrence:
And then I followed with:
However this is the part where I got stuck:
I have absolutely no idea of how to resolve that sum, I tried applying logarithm properties to get a difference instead of division and then make two separated and simplier sums, but I still couldn't find or figure out if I can use any summation identities.
recurrence-relations recursion
asked Jan 24 at 8:16
MikeKatz45MikeKatz45
399
$endgroup$
|
show 2 more comments
$begingroup$
I've seen plenty of discussion regarding solving recurrences like this with the master theorem, but I need to solve it via back substitution. Was doing pretty good until I got stuck in the summation part.
Assumptions are that $n$ is a power of $3$ so $n = 3^k$ and hence $k = log_3(n)$. Also $T(1) = 1$.
After substituting $3$ functions to recognize the pattern I found this general form for the recurrence:
And then I followed with:
However this is the part where I got stuck:
I have absolutely no idea of how to resolve that sum, I tried applying logarithm properties to get a difference instead of division and then make two separated and simplier sums, but I still couldn't find or figure out if I can use any summation identities.
recurrence-relations recursion
asked Jan 24 at 8:16
MikeKatz45MikeKatz45
399
$endgroup$
$begingroup$
Note that $$sum_{i=0}^{k-1}log_3left(frac n{3^i}right)=sum_{i=0}^{k-1}(log_3 n-i)=klog_3n-sum_{i=0}^{k-1}i$$ hence $$sum_{i=0}^{k-1}log_3left(frac n{3^i}right)=klog_3n-frac{k(k-1)}2$$
$endgroup$
– Did
Jan 26 at 19:12
$begingroup$
Why are you able to take log3(n) out of the summation without writing it in sigma notation again? Where does the k multiplying that come from? D:
$endgroup$
– MikeKatz45
Jan 26 at 19:24
1
$begingroup$
Because $log_3n$ does not depend on $i$. And because there are $k$ terms in the sum. For every number $c$ independent of $i$, $$sum_{i=0}^{k-1}c=c,k$$
$endgroup$
– Did
Jan 26 at 19:27
$begingroup$
that means log3(n) could be treated as a constant? or does "constant" in this case just means not dependant on the sum index?
$endgroup$
– MikeKatz45
Jan 26 at 19:35
$begingroup$
Either one you prefer.
$endgroup$
– Did
Jan 26 at 19:37
|
show 2 more comments
$begingroup$
I've seen plenty of discussion regarding solving recurrences like this with the master theorem, but I need to solve it via back substitution. Was doing pretty good until I got stuck in the summation part.
Assumptions are that $n$ is a power of $3$ so $n = 3^k$ and hence $k = log_3(n)$. Also $T(1) = 1$.
After substituting $3$ functions to recognize the pattern I found this general form for the recurrence:
And then I followed with:
However this is the part where I got stuck:
I have absolutely no idea of how to resolve that sum, I tried applying logarithm properties to get a difference instead of division and then make two separated and simplier sums, but I still couldn't find or figure out if I can use any summation identities.
recurrence-relations recursion
asked Jan 24 at 8:16
MikeKatz45MikeKatz45
399
$endgroup$
I've seen plenty of discussion regarding solving recurrences like this with the master theorem, but I need to solve it via back substitution. Was doing pretty good until I got stuck in the summation part.
Assumptions are that $n$ is a power of $3$ so $n = 3^k$ and hence $k = log_3(n)$. Also $T(1) = 1$.
After substituting $3$ functions to recognize the pattern I found this general form for the recurrence:
And then I followed with:
However this is the part where I got stuck:
I have absolutely no idea of how to resolve that sum, I tried applying logarithm properties to get a difference instead of division and then make two separated and simplier sums, but I still couldn't find or figure out if I can use any summation identities.
recurrence-relations recursion
recurrence-relations recursion
asked Jan 24 at 8:16
MikeKatz45MikeKatz45
399
asked Jan 24 at 8:16
MikeKatz45MikeKatz45
399
edited Jan 27 at 18:23
MikeKatz45
asked Jan 24 at 8:16
MikeKatz45MikeKatz45
399
asked Jan 24 at 8:16
MikeKatz45MikeKatz45
399
asked Jan 24 at 8:16
MikeKatz45MikeKatz45
399
399
$begingroup$
Note that $$sum_{i=0}^{k-1}log_3left(frac n{3^i}right)=sum_{i=0}^{k-1}(log_3 n-i)=klog_3n-sum_{i=0}^{k-1}i$$ hence $$sum_{i=0}^{k-1}log_3left(frac n{3^i}right)=klog_3n-frac{k(k-1)}2$$
$endgroup$
– Did
Jan 26 at 19:12
$begingroup$
Why are you able to take log3(n) out of the summation without writing it in sigma notation again? Where does the k multiplying that come from? D:
$endgroup$
– MikeKatz45
Jan 26 at 19:24
1
$begingroup$
Because $log_3n$ does not depend on $i$. And because there are $k$ terms in the sum. For every number $c$ independent of $i$, $$sum_{i=0}^{k-1}c=c,k$$
$endgroup$
– Did
Jan 26 at 19:27
$begingroup$
that means log3(n) could be treated as a constant? or does "constant" in this case just means not dependant on the sum index?
$endgroup$
– MikeKatz45
Jan 26 at 19:35
$begingroup$
Either one you prefer.
$endgroup$
– Did
Jan 26 at 19:37
|
show 2 more comments
$begingroup$
Note that $$sum_{i=0}^{k-1}log_3left(frac n{3^i}right)=sum_{i=0}^{k-1}(log_3 n-i)=klog_3n-sum_{i=0}^{k-1}i$$ hence $$sum_{i=0}^{k-1}log_3left(frac n{3^i}right)=klog_3n-frac{k(k-1)}2$$
$endgroup$
– Did
Jan 26 at 19:12
$begingroup$
Why are you able to take log3(n) out of the summation without writing it in sigma notation again? Where does the k multiplying that come from? D:
$endgroup$
– MikeKatz45
Jan 26 at 19:24
1
$begingroup$
Because $log_3n$ does not depend on $i$. And because there are $k$ terms in the sum. For every number $c$ independent of $i$, $$sum_{i=0}^{k-1}c=c,k$$
$endgroup$
– Did
Jan 26 at 19:27
$begingroup$
that means log3(n) could be treated as a constant? or does "constant" in this case just means not dependant on the sum index?
$endgroup$
– MikeKatz45
Jan 26 at 19:35
$begingroup$
Either one you prefer.
$endgroup$
– Did
Jan 26 at 19:37
$begingroup$
Note that $$sum_{i=0}^{k-1}log_3left(frac n{3^i}right)=sum_{i=0}^{k-1}(log_3 n-i)=klog_3n-sum_{i=0}^{k-1}i$$ hence $$sum_{i=0}^{k-1}log_3left(frac n{3^i}right)=klog_3n-frac{k(k-1)}2$$
$endgroup$
– Did
Jan 26 at 19:12
$begingroup$
Note that $$sum_{i=0}^{k-1}log_3left(frac n{3^i}right)=sum_{i=0}^{k-1}(log_3 n-i)=klog_3n-sum_{i=0}^{k-1}i$$ hence $$sum_{i=0}^{k-1}log_3left(frac n{3^i}right)=klog_3n-frac{k(k-1)}2$$
$endgroup$
– Did
Jan 26 at 19:12
$begingroup$
Why are you able to take log3(n) out of the summation without writing it in sigma notation again? Where does the k multiplying that come from? D:
$endgroup$
– MikeKatz45
Jan 26 at 19:24
$begingroup$
Why are you able to take log3(n) out of the summation without writing it in sigma notation again? Where does the k multiplying that come from? D:
$endgroup$
– MikeKatz45
Jan 26 at 19:24
1
1
$begingroup$
Because $log_3n$ does not depend on $i$. And because there are $k$ terms in the sum. For every number $c$ independent of $i$, $$sum_{i=0}^{k-1}c=c,k$$
$endgroup$
– Did
Jan 26 at 19:27
$begingroup$
Because $log_3n$ does not depend on $i$. And because there are $k$ terms in the sum. For every number $c$ independent of $i$, $$sum_{i=0}^{k-1}c=c,k$$
$endgroup$
– Did
Jan 26 at 19:27
$begingroup$
that means log3(n) could be treated as a constant? or does "constant" in this case just means not dependant on the sum index?
$endgroup$
– MikeKatz45
Jan 26 at 19:35
$begingroup$
that means log3(n) could be treated as a constant? or does "constant" in this case just means not dependant on the sum index?
$endgroup$
– MikeKatz45
Jan 26 at 19:35
$begingroup$
Either one you prefer.
$endgroup$
– Did
Jan 26 at 19:37
$begingroup$
Either one you prefer.
$endgroup$
– Did
Jan 26 at 19:37
|
show 2 more comments
2 Answers
2
active
oldest
votes
$begingroup$
I will redo the work from begginning also using $lg x=log_2 x$ as binary logarithm.
First I will iterate the first term, then later combine it with the sum which the second term gave:$$T(n)=3Tleft(frac{n}{3}right)+nlg n$$
$$3Tleft(frac{n}{3}right)=3left(3Tleft(frac{n}{3^2}right)+frac{n}{3}lgfrac{n}{3}right)=3^2Tleft(frac{n}{3^2}right)+nlgfrac{n}{3}$$
$$3^2Tleft(frac{n}{3^2}right)=3^2left(3Tleft(frac{n}{3^3}right)+frac{n}{3^2}lgfrac{n}{3^2}right)=3^3Tleft(frac{n}{3^3}right)+nlgfrac{n}{3^2}$$
$$dots$$
$$3^{k-1}Tleft(frac{n}{3^{k-1}}right)=3^kTleft(frac{n}{3^k}right)+nlgfrac{n}{3^{k-1}}$$
The recursion ends when we hit $T(1)$, thus we can take $k$ from there:
$$Tleft(frac{n}{3^k}right)=T(1)Rightarrow n=3^kRightarrow k=log_3n$$
$$Rightarrow T(n)=3^k cdot underbrace{T(1)}_{=1}+nlg n +nlgfrac{n}{3}+dots+nlgfrac{n}{3^{k-1}}$$
$$=underbrace{3^{log_3 n}}_{=n} cdot 1 +sum_{i=0}^{k-1}n lgfrac{n}{3^{i}}=n+nsum_{i=0}^{k-1}left(lg n-lg3^{i}right),quad quad a^{log_a b}=b^{log_a a}$$
$$=n+nlg n sum_{i=0}^{k-1}1-nsum_{i=0}^{k-1}i cdot lg 3, quad quad lg a^b = blg a$$
$$=n+nlg n cdot k -nlg 3 cdot frac{(k-1)k}{2}$$
$$=n+nlg n cdot frac{lg n}{lg 3}-frac{lg 3}{2}nleft(frac{lg n}{lg 3}-1right)frac{lg n}{lg 3},quad quad k=log_3 n =frac{lg n}{lg 3}$$
$$=n+frac{1}{lg 3} nlg^2 n -frac12 frac{1}{lg 3}nlg^2 n+frac12 nlg n$$
$$boxed{T(n)=n+frac1{2log_2 3} nlog_2^2 n +frac12 nlog_2 n}$$
answered Jan 26 at 19:31
ZackyZacky
7,88511061
$endgroup$
1
$begingroup$
I tried to follow from where I got stuck, but I got a slightly different result. Could you check my edit at the end of my question and check if I missed something? I think you missed multiplying by lg3 in one of the denominators, but it could be my mistake too
$endgroup$
– MikeKatz45
Jan 27 at 3:20
$begingroup$
@MikeKatz45 Yes, I forgot to multiply there by the red factor: $$frac{lg 3}{2}nleft(frac{lg n}{lg 3}-1right)frac{lg n}{color{red}{lg 3}}$$ Also note that you have a minus sign when you mutiply by $1$, thus the last term will have a plus.
$endgroup$
– Zacky
Jan 27 at 9:54
1
$begingroup$
Excellent thank you very much, it took me a while to follow your proceedure, but I understand everything now (:
$endgroup$
– MikeKatz45
Jan 27 at 18:21
add a comment |
$begingroup$
Considering from $T(n)-3T(frac n3)=nlog_2 n$
$$
mathcal{T}(log_3 n)-3mathcal{T}(log_3(frac n3))=nlog_2 n
$$
or
$$
mathcal{T}(log_3 n)-3mathcal{T}(log_3 n -1))=nlog_2 n
$$
then making $z = log_3 n$ we have the linear difference equation
$$
mathcal{T}(z)-3mathcal{T}(z -1)=3^zlog_2 3^z = z 3^zlog_2 3
$$
The solution can be represented as
$$
mathcal{T} = mathcal{T}_h+ mathcal{T}_p
$$
such that
$$
mathcal{T}_h(z)-3mathcal{T}_h(z -1)=0\
mathcal{T}_p(z)-3mathcal{T}_p(z -1)=z 3^zlog_2 3
$$
but
$$
mathcal{T}_h(z) = C 3^{z-1}
$$
now substituting $mathcal{T}_p(z) = C(z) 3^{z-1}$ into the particular equation (variation of constants as with DE's) we obtain
$$
C(z)-C(z-1) = z^2 3^{2-z}log_2 3
$$
and then
$$
C(z) = frac 12 3^{3-z}left(3^z-z-frac{z^2}{3}-1right)log_2 3
$$
and finally
$$
mathcal{T} = C 3^{z-1}+left( frac 12 3^{3-z}left(3^z-z-frac{z^2}{3}-1right)log_2 3right)3^{z-1}
$$
etc.
answered Jan 27 at 15:16
CesareoCesareo
9,4673517
$endgroup$
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%2f3085606%2fsolving-the-recurrence-tn-3t-left-fracn3-right-n-log-2-n%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 will redo the work from begginning also using $lg x=log_2 x$ as binary logarithm.
First I will iterate the first term, then later combine it with the sum which the second term gave:$$T(n)=3Tleft(frac{n}{3}right)+nlg n$$
$$3Tleft(frac{n}{3}right)=3left(3Tleft(frac{n}{3^2}right)+frac{n}{3}lgfrac{n}{3}right)=3^2Tleft(frac{n}{3^2}right)+nlgfrac{n}{3}$$
$$3^2Tleft(frac{n}{3^2}right)=3^2left(3Tleft(frac{n}{3^3}right)+frac{n}{3^2}lgfrac{n}{3^2}right)=3^3Tleft(frac{n}{3^3}right)+nlgfrac{n}{3^2}$$
$$dots$$
$$3^{k-1}Tleft(frac{n}{3^{k-1}}right)=3^kTleft(frac{n}{3^k}right)+nlgfrac{n}{3^{k-1}}$$
The recursion ends when we hit $T(1)$, thus we can take $k$ from there:
$$Tleft(frac{n}{3^k}right)=T(1)Rightarrow n=3^kRightarrow k=log_3n$$
$$Rightarrow T(n)=3^k cdot underbrace{T(1)}_{=1}+nlg n +nlgfrac{n}{3}+dots+nlgfrac{n}{3^{k-1}}$$
$$=underbrace{3^{log_3 n}}_{=n} cdot 1 +sum_{i=0}^{k-1}n lgfrac{n}{3^{i}}=n+nsum_{i=0}^{k-1}left(lg n-lg3^{i}right),quad quad a^{log_a b}=b^{log_a a}$$
$$=n+nlg n sum_{i=0}^{k-1}1-nsum_{i=0}^{k-1}i cdot lg 3, quad quad lg a^b = blg a$$
$$=n+nlg n cdot k -nlg 3 cdot frac{(k-1)k}{2}$$
$$=n+nlg n cdot frac{lg n}{lg 3}-frac{lg 3}{2}nleft(frac{lg n}{lg 3}-1right)frac{lg n}{lg 3},quad quad k=log_3 n =frac{lg n}{lg 3}$$
$$=n+frac{1}{lg 3} nlg^2 n -frac12 frac{1}{lg 3}nlg^2 n+frac12 nlg n$$
$$boxed{T(n)=n+frac1{2log_2 3} nlog_2^2 n +frac12 nlog_2 n}$$
answered Jan 26 at 19:31
ZackyZacky
7,88511061
$endgroup$
1
$begingroup$
I tried to follow from where I got stuck, but I got a slightly different result. Could you check my edit at the end of my question and check if I missed something? I think you missed multiplying by lg3 in one of the denominators, but it could be my mistake too
$endgroup$
– MikeKatz45
Jan 27 at 3:20
$begingroup$
@MikeKatz45 Yes, I forgot to multiply there by the red factor: $$frac{lg 3}{2}nleft(frac{lg n}{lg 3}-1right)frac{lg n}{color{red}{lg 3}}$$ Also note that you have a minus sign when you mutiply by $1$, thus the last term will have a plus.
$endgroup$
– Zacky
Jan 27 at 9:54
1
$begingroup$
Excellent thank you very much, it took me a while to follow your proceedure, but I understand everything now (:
$endgroup$
– MikeKatz45
Jan 27 at 18:21
add a comment |
$begingroup$
I will redo the work from begginning also using $lg x=log_2 x$ as binary logarithm.
First I will iterate the first term, then later combine it with the sum which the second term gave:$$T(n)=3Tleft(frac{n}{3}right)+nlg n$$
$$3Tleft(frac{n}{3}right)=3left(3Tleft(frac{n}{3^2}right)+frac{n}{3}lgfrac{n}{3}right)=3^2Tleft(frac{n}{3^2}right)+nlgfrac{n}{3}$$
$$3^2Tleft(frac{n}{3^2}right)=3^2left(3Tleft(frac{n}{3^3}right)+frac{n}{3^2}lgfrac{n}{3^2}right)=3^3Tleft(frac{n}{3^3}right)+nlgfrac{n}{3^2}$$
$$dots$$
$$3^{k-1}Tleft(frac{n}{3^{k-1}}right)=3^kTleft(frac{n}{3^k}right)+nlgfrac{n}{3^{k-1}}$$
The recursion ends when we hit $T(1)$, thus we can take $k$ from there:
$$Tleft(frac{n}{3^k}right)=T(1)Rightarrow n=3^kRightarrow k=log_3n$$
$$Rightarrow T(n)=3^k cdot underbrace{T(1)}_{=1}+nlg n +nlgfrac{n}{3}+dots+nlgfrac{n}{3^{k-1}}$$
$$=underbrace{3^{log_3 n}}_{=n} cdot 1 +sum_{i=0}^{k-1}n lgfrac{n}{3^{i}}=n+nsum_{i=0}^{k-1}left(lg n-lg3^{i}right),quad quad a^{log_a b}=b^{log_a a}$$
$$=n+nlg n sum_{i=0}^{k-1}1-nsum_{i=0}^{k-1}i cdot lg 3, quad quad lg a^b = blg a$$
$$=n+nlg n cdot k -nlg 3 cdot frac{(k-1)k}{2}$$
$$=n+nlg n cdot frac{lg n}{lg 3}-frac{lg 3}{2}nleft(frac{lg n}{lg 3}-1right)frac{lg n}{lg 3},quad quad k=log_3 n =frac{lg n}{lg 3}$$
$$=n+frac{1}{lg 3} nlg^2 n -frac12 frac{1}{lg 3}nlg^2 n+frac12 nlg n$$
$$boxed{T(n)=n+frac1{2log_2 3} nlog_2^2 n +frac12 nlog_2 n}$$
answered Jan 26 at 19:31
ZackyZacky
7,88511061
$endgroup$
1
$begingroup$
I tried to follow from where I got stuck, but I got a slightly different result. Could you check my edit at the end of my question and check if I missed something? I think you missed multiplying by lg3 in one of the denominators, but it could be my mistake too
$endgroup$
– MikeKatz45
Jan 27 at 3:20
$begingroup$
@MikeKatz45 Yes, I forgot to multiply there by the red factor: $$frac{lg 3}{2}nleft(frac{lg n}{lg 3}-1right)frac{lg n}{color{red}{lg 3}}$$ Also note that you have a minus sign when you mutiply by $1$, thus the last term will have a plus.
$endgroup$
– Zacky
Jan 27 at 9:54
1
$begingroup$
Excellent thank you very much, it took me a while to follow your proceedure, but I understand everything now (:
$endgroup$
– MikeKatz45
Jan 27 at 18:21
add a comment |
$begingroup$
I will redo the work from begginning also using $lg x=log_2 x$ as binary logarithm.
First I will iterate the first term, then later combine it with the sum which the second term gave:$$T(n)=3Tleft(frac{n}{3}right)+nlg n$$
$$3Tleft(frac{n}{3}right)=3left(3Tleft(frac{n}{3^2}right)+frac{n}{3}lgfrac{n}{3}right)=3^2Tleft(frac{n}{3^2}right)+nlgfrac{n}{3}$$
$$3^2Tleft(frac{n}{3^2}right)=3^2left(3Tleft(frac{n}{3^3}right)+frac{n}{3^2}lgfrac{n}{3^2}right)=3^3Tleft(frac{n}{3^3}right)+nlgfrac{n}{3^2}$$
$$dots$$
$$3^{k-1}Tleft(frac{n}{3^{k-1}}right)=3^kTleft(frac{n}{3^k}right)+nlgfrac{n}{3^{k-1}}$$
The recursion ends when we hit $T(1)$, thus we can take $k$ from there:
$$Tleft(frac{n}{3^k}right)=T(1)Rightarrow n=3^kRightarrow k=log_3n$$
$$Rightarrow T(n)=3^k cdot underbrace{T(1)}_{=1}+nlg n +nlgfrac{n}{3}+dots+nlgfrac{n}{3^{k-1}}$$
$$=underbrace{3^{log_3 n}}_{=n} cdot 1 +sum_{i=0}^{k-1}n lgfrac{n}{3^{i}}=n+nsum_{i=0}^{k-1}left(lg n-lg3^{i}right),quad quad a^{log_a b}=b^{log_a a}$$
$$=n+nlg n sum_{i=0}^{k-1}1-nsum_{i=0}^{k-1}i cdot lg 3, quad quad lg a^b = blg a$$
$$=n+nlg n cdot k -nlg 3 cdot frac{(k-1)k}{2}$$
$$=n+nlg n cdot frac{lg n}{lg 3}-frac{lg 3}{2}nleft(frac{lg n}{lg 3}-1right)frac{lg n}{lg 3},quad quad k=log_3 n =frac{lg n}{lg 3}$$
$$=n+frac{1}{lg 3} nlg^2 n -frac12 frac{1}{lg 3}nlg^2 n+frac12 nlg n$$
$$boxed{T(n)=n+frac1{2log_2 3} nlog_2^2 n +frac12 nlog_2 n}$$
answered Jan 26 at 19:31
ZackyZacky
7,88511061
$endgroup$
I will redo the work from begginning also using $lg x=log_2 x$ as binary logarithm.
First I will iterate the first term, then later combine it with the sum which the second term gave:$$T(n)=3Tleft(frac{n}{3}right)+nlg n$$
$$3Tleft(frac{n}{3}right)=3left(3Tleft(frac{n}{3^2}right)+frac{n}{3}lgfrac{n}{3}right)=3^2Tleft(frac{n}{3^2}right)+nlgfrac{n}{3}$$
$$3^2Tleft(frac{n}{3^2}right)=3^2left(3Tleft(frac{n}{3^3}right)+frac{n}{3^2}lgfrac{n}{3^2}right)=3^3Tleft(frac{n}{3^3}right)+nlgfrac{n}{3^2}$$
$$dots$$
$$3^{k-1}Tleft(frac{n}{3^{k-1}}right)=3^kTleft(frac{n}{3^k}right)+nlgfrac{n}{3^{k-1}}$$
The recursion ends when we hit $T(1)$, thus we can take $k$ from there:
$$Tleft(frac{n}{3^k}right)=T(1)Rightarrow n=3^kRightarrow k=log_3n$$
$$Rightarrow T(n)=3^k cdot underbrace{T(1)}_{=1}+nlg n +nlgfrac{n}{3}+dots+nlgfrac{n}{3^{k-1}}$$
$$=underbrace{3^{log_3 n}}_{=n} cdot 1 +sum_{i=0}^{k-1}n lgfrac{n}{3^{i}}=n+nsum_{i=0}^{k-1}left(lg n-lg3^{i}right),quad quad a^{log_a b}=b^{log_a a}$$
$$=n+nlg n sum_{i=0}^{k-1}1-nsum_{i=0}^{k-1}i cdot lg 3, quad quad lg a^b = blg a$$
$$=n+nlg n cdot k -nlg 3 cdot frac{(k-1)k}{2}$$
$$=n+nlg n cdot frac{lg n}{lg 3}-frac{lg 3}{2}nleft(frac{lg n}{lg 3}-1right)frac{lg n}{lg 3},quad quad k=log_3 n =frac{lg n}{lg 3}$$
$$=n+frac{1}{lg 3} nlg^2 n -frac12 frac{1}{lg 3}nlg^2 n+frac12 nlg n$$
$$boxed{T(n)=n+frac1{2log_2 3} nlog_2^2 n +frac12 nlog_2 n}$$
answered Jan 26 at 19:31
ZackyZacky
7,88511061
edited Jan 27 at 9:53
answered Jan 26 at 19:31
ZackyZacky
7,88511061
answered Jan 26 at 19:31
ZackyZacky
7,88511061
answered Jan 26 at 19:31
ZackyZacky
7,88511061
7,88511061
1
$begingroup$
I tried to follow from where I got stuck, but I got a slightly different result. Could you check my edit at the end of my question and check if I missed something? I think you missed multiplying by lg3 in one of the denominators, but it could be my mistake too
$endgroup$
– MikeKatz45
Jan 27 at 3:20
$begingroup$
@MikeKatz45 Yes, I forgot to multiply there by the red factor: $$frac{lg 3}{2}nleft(frac{lg n}{lg 3}-1right)frac{lg n}{color{red}{lg 3}}$$ Also note that you have a minus sign when you mutiply by $1$, thus the last term will have a plus.
$endgroup$
– Zacky
Jan 27 at 9:54
1
$begingroup$
Excellent thank you very much, it took me a while to follow your proceedure, but I understand everything now (:
$endgroup$
– MikeKatz45
Jan 27 at 18:21
add a comment |
1
$begingroup$
I tried to follow from where I got stuck, but I got a slightly different result. Could you check my edit at the end of my question and check if I missed something? I think you missed multiplying by lg3 in one of the denominators, but it could be my mistake too
$endgroup$
– MikeKatz45
Jan 27 at 3:20
$begingroup$
@MikeKatz45 Yes, I forgot to multiply there by the red factor: $$frac{lg 3}{2}nleft(frac{lg n}{lg 3}-1right)frac{lg n}{color{red}{lg 3}}$$ Also note that you have a minus sign when you mutiply by $1$, thus the last term will have a plus.
$endgroup$
– Zacky
Jan 27 at 9:54
1
$begingroup$
Excellent thank you very much, it took me a while to follow your proceedure, but I understand everything now (:
$endgroup$
– MikeKatz45
Jan 27 at 18:21
1
1
$begingroup$
I tried to follow from where I got stuck, but I got a slightly different result. Could you check my edit at the end of my question and check if I missed something? I think you missed multiplying by lg3 in one of the denominators, but it could be my mistake too
$endgroup$
– MikeKatz45
Jan 27 at 3:20
$begingroup$
I tried to follow from where I got stuck, but I got a slightly different result. Could you check my edit at the end of my question and check if I missed something? I think you missed multiplying by lg3 in one of the denominators, but it could be my mistake too
$endgroup$
– MikeKatz45
Jan 27 at 3:20
$begingroup$
@MikeKatz45 Yes, I forgot to multiply there by the red factor: $$frac{lg 3}{2}nleft(frac{lg n}{lg 3}-1right)frac{lg n}{color{red}{lg 3}}$$ Also note that you have a minus sign when you mutiply by $1$, thus the last term will have a plus.
$endgroup$
– Zacky
Jan 27 at 9:54
$begingroup$
@MikeKatz45 Yes, I forgot to multiply there by the red factor: $$frac{lg 3}{2}nleft(frac{lg n}{lg 3}-1right)frac{lg n}{color{red}{lg 3}}$$ Also note that you have a minus sign when you mutiply by $1$, thus the last term will have a plus.
$endgroup$
– Zacky
Jan 27 at 9:54
1
1
$begingroup$
Excellent thank you very much, it took me a while to follow your proceedure, but I understand everything now (:
$endgroup$
– MikeKatz45
Jan 27 at 18:21
$begingroup$
Excellent thank you very much, it took me a while to follow your proceedure, but I understand everything now (:
$endgroup$
– MikeKatz45
Jan 27 at 18:21
add a comment |
$begingroup$
Considering from $T(n)-3T(frac n3)=nlog_2 n$
$$
mathcal{T}(log_3 n)-3mathcal{T}(log_3(frac n3))=nlog_2 n
$$
or
$$
mathcal{T}(log_3 n)-3mathcal{T}(log_3 n -1))=nlog_2 n
$$
then making $z = log_3 n$ we have the linear difference equation
$$
mathcal{T}(z)-3mathcal{T}(z -1)=3^zlog_2 3^z = z 3^zlog_2 3
$$
The solution can be represented as
$$
mathcal{T} = mathcal{T}_h+ mathcal{T}_p
$$
such that
$$
mathcal{T}_h(z)-3mathcal{T}_h(z -1)=0\
mathcal{T}_p(z)-3mathcal{T}_p(z -1)=z 3^zlog_2 3
$$
but
$$
mathcal{T}_h(z) = C 3^{z-1}
$$
now substituting $mathcal{T}_p(z) = C(z) 3^{z-1}$ into the particular equation (variation of constants as with DE's) we obtain
$$
C(z)-C(z-1) = z^2 3^{2-z}log_2 3
$$
and then
$$
C(z) = frac 12 3^{3-z}left(3^z-z-frac{z^2}{3}-1right)log_2 3
$$
and finally
$$
mathcal{T} = C 3^{z-1}+left( frac 12 3^{3-z}left(3^z-z-frac{z^2}{3}-1right)log_2 3right)3^{z-1}
$$
etc.
answered Jan 27 at 15:16
CesareoCesareo
9,4673517
$endgroup$
add a comment |
$begingroup$
Considering from $T(n)-3T(frac n3)=nlog_2 n$
$$
mathcal{T}(log_3 n)-3mathcal{T}(log_3(frac n3))=nlog_2 n
$$
or
$$
mathcal{T}(log_3 n)-3mathcal{T}(log_3 n -1))=nlog_2 n
$$
then making $z = log_3 n$ we have the linear difference equation
$$
mathcal{T}(z)-3mathcal{T}(z -1)=3^zlog_2 3^z = z 3^zlog_2 3
$$
The solution can be represented as
$$
mathcal{T} = mathcal{T}_h+ mathcal{T}_p
$$
such that
$$
mathcal{T}_h(z)-3mathcal{T}_h(z -1)=0\
mathcal{T}_p(z)-3mathcal{T}_p(z -1)=z 3^zlog_2 3
$$
but
$$
mathcal{T}_h(z) = C 3^{z-1}
$$
now substituting $mathcal{T}_p(z) = C(z) 3^{z-1}$ into the particular equation (variation of constants as with DE's) we obtain
$$
C(z)-C(z-1) = z^2 3^{2-z}log_2 3
$$
and then
$$
C(z) = frac 12 3^{3-z}left(3^z-z-frac{z^2}{3}-1right)log_2 3
$$
and finally
$$
mathcal{T} = C 3^{z-1}+left( frac 12 3^{3-z}left(3^z-z-frac{z^2}{3}-1right)log_2 3right)3^{z-1}
$$
etc.
answered Jan 27 at 15:16
CesareoCesareo
9,4673517
$endgroup$
add a comment |
$begingroup$
Considering from $T(n)-3T(frac n3)=nlog_2 n$
$$
mathcal{T}(log_3 n)-3mathcal{T}(log_3(frac n3))=nlog_2 n
$$
or
$$
mathcal{T}(log_3 n)-3mathcal{T}(log_3 n -1))=nlog_2 n
$$
then making $z = log_3 n$ we have the linear difference equation
$$
mathcal{T}(z)-3mathcal{T}(z -1)=3^zlog_2 3^z = z 3^zlog_2 3
$$
The solution can be represented as
$$
mathcal{T} = mathcal{T}_h+ mathcal{T}_p
$$
such that
$$
mathcal{T}_h(z)-3mathcal{T}_h(z -1)=0\
mathcal{T}_p(z)-3mathcal{T}_p(z -1)=z 3^zlog_2 3
$$
but
$$
mathcal{T}_h(z) = C 3^{z-1}
$$
now substituting $mathcal{T}_p(z) = C(z) 3^{z-1}$ into the particular equation (variation of constants as with DE's) we obtain
$$
C(z)-C(z-1) = z^2 3^{2-z}log_2 3
$$
and then
$$
C(z) = frac 12 3^{3-z}left(3^z-z-frac{z^2}{3}-1right)log_2 3
$$
and finally
$$
mathcal{T} = C 3^{z-1}+left( frac 12 3^{3-z}left(3^z-z-frac{z^2}{3}-1right)log_2 3right)3^{z-1}
$$
etc.
answered Jan 27 at 15:16
CesareoCesareo
9,4673517
$endgroup$
Considering from $T(n)-3T(frac n3)=nlog_2 n$
$$
mathcal{T}(log_3 n)-3mathcal{T}(log_3(frac n3))=nlog_2 n
$$
or
$$
mathcal{T}(log_3 n)-3mathcal{T}(log_3 n -1))=nlog_2 n
$$
then making $z = log_3 n$ we have the linear difference equation
$$
mathcal{T}(z)-3mathcal{T}(z -1)=3^zlog_2 3^z = z 3^zlog_2 3
$$
The solution can be represented as
$$
mathcal{T} = mathcal{T}_h+ mathcal{T}_p
$$
such that
$$
mathcal{T}_h(z)-3mathcal{T}_h(z -1)=0\
mathcal{T}_p(z)-3mathcal{T}_p(z -1)=z 3^zlog_2 3
$$
but
$$
mathcal{T}_h(z) = C 3^{z-1}
$$
now substituting $mathcal{T}_p(z) = C(z) 3^{z-1}$ into the particular equation (variation of constants as with DE's) we obtain
$$
C(z)-C(z-1) = z^2 3^{2-z}log_2 3
$$
and then
$$
C(z) = frac 12 3^{3-z}left(3^z-z-frac{z^2}{3}-1right)log_2 3
$$
and finally
$$
mathcal{T} = C 3^{z-1}+left( frac 12 3^{3-z}left(3^z-z-frac{z^2}{3}-1right)log_2 3right)3^{z-1}
$$
etc.
answered Jan 27 at 15:16
CesareoCesareo
9,4673517
answered Jan 27 at 15:16
CesareoCesareo
9,4673517
answered Jan 27 at 15:16
CesareoCesareo
9,4673517
answered Jan 27 at 15:16
CesareoCesareo
9,4673517
9,4673517
add a comment |
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%2f3085606%2fsolving-the-recurrence-tn-3t-left-fracn3-right-n-log-2-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$
Note that $$sum_{i=0}^{k-1}log_3left(frac n{3^i}right)=sum_{i=0}^{k-1}(log_3 n-i)=klog_3n-sum_{i=0}^{k-1}i$$ hence $$sum_{i=0}^{k-1}log_3left(frac n{3^i}right)=klog_3n-frac{k(k-1)}2$$
$endgroup$
– Did
Jan 26 at 19:12
$begingroup$
Why are you able to take log3(n) out of the summation without writing it in sigma notation again? Where does the k multiplying that come from? D:
$endgroup$
– MikeKatz45
Jan 26 at 19:24
1
$begingroup$
Because $log_3n$ does not depend on $i$. And because there are $k$ terms in the sum. For every number $c$ independent of $i$, $$sum_{i=0}^{k-1}c=c,k$$
$endgroup$
– Did
Jan 26 at 19:27
$begingroup$
that means log3(n) could be treated as a constant? or does "constant" in this case just means not dependant on the sum index?
$endgroup$
– MikeKatz45
Jan 26 at 19:35
$begingroup$
Either one you prefer.
$endgroup$
– Did
Jan 26 at 19:37