Asymptotic behaviour of recurrence
In DNA chain, there are four types of bases: A, C, G, T. Let $g(n)$ be the number of configurations of a DNA chain of length $n$, in which the sequences TT and TG never appear. Write a recurrence for $g(n)$. Determine the asymptotic behavior of the recurrence. Also, prove whether this rate of growth is $o(n^{ n^{1/2}}), Theta(n^{ n^{1/2}}),$ or $Omega(n^{ n^{1/2}})$.
My answer:
$g(n)=A(n)+C(n)+G(n)+T(n)$
$g(n)=g(n-1)+g(n-1)+g(n-1)+A(n-1)+C(n-1)$
$g(n)=3g(n-1)+2g(n-2)$
After solving this recurrence, we get
$$begin{align}
g(n) &= (frac{(4)(17)^{1/2}+16}{(3)(17)^{1/2}+17})(frac{3+(17)^{1/2})}{2})^n \
&+(frac{(17)^{1/2}-5)}{2(17)^{1/2}})(frac{3-(17)^{1/2}}{2})^n
end{align}$$
Therefore when $n$ is large, $(frac{3-(17)^{1/2})}{2})^n$ become smaller and smaller
So we can write $$g(n) = Theta((frac{3+(17)^{1/2})}{2})^n).$$
(Do I determine the asymptotic behavior of the recurrence correctly?)
But I do not know what is the rate of growth, if we take the limit of $frac{g(n)}{n^{ n^{1/2}}}$,where n tend to infinity, it seems impossible to calculate it. How could I determine the rate of growth?
discrete-mathematics asymptotics biology
add a comment |
In DNA chain, there are four types of bases: A, C, G, T. Let $g(n)$ be the number of configurations of a DNA chain of length $n$, in which the sequences TT and TG never appear. Write a recurrence for $g(n)$. Determine the asymptotic behavior of the recurrence. Also, prove whether this rate of growth is $o(n^{ n^{1/2}}), Theta(n^{ n^{1/2}}),$ or $Omega(n^{ n^{1/2}})$.
My answer:
$g(n)=A(n)+C(n)+G(n)+T(n)$
$g(n)=g(n-1)+g(n-1)+g(n-1)+A(n-1)+C(n-1)$
$g(n)=3g(n-1)+2g(n-2)$
After solving this recurrence, we get
$$begin{align}
g(n) &= (frac{(4)(17)^{1/2}+16}{(3)(17)^{1/2}+17})(frac{3+(17)^{1/2})}{2})^n \
&+(frac{(17)^{1/2}-5)}{2(17)^{1/2}})(frac{3-(17)^{1/2}}{2})^n
end{align}$$
Therefore when $n$ is large, $(frac{3-(17)^{1/2})}{2})^n$ become smaller and smaller
So we can write $$g(n) = Theta((frac{3+(17)^{1/2})}{2})^n).$$
(Do I determine the asymptotic behavior of the recurrence correctly?)
But I do not know what is the rate of growth, if we take the limit of $frac{g(n)}{n^{ n^{1/2}}}$,where n tend to infinity, it seems impossible to calculate it. How could I determine the rate of growth?
discrete-mathematics asymptotics biology
Write, for example,$Theta$
for $Theta$; this is what's known as MathJax, a type of $LaTeX$.
– Shaun
Nov 26 at 15:56
Use$frac{a}{b}$
for $frac{a}{b}$.
– Shaun
Nov 26 at 15:58
Please edit the question.
– Shaun
Nov 26 at 15:59
The exercise is strange because it has a much simpler solution. Namely, note that the total number of configurations is $4^n$ hence $g(n)leqslant4^n$. Since $4^n=o(n^{sqrt n})$, you are done.
– Did
Dec 12 at 9:18
add a comment |
In DNA chain, there are four types of bases: A, C, G, T. Let $g(n)$ be the number of configurations of a DNA chain of length $n$, in which the sequences TT and TG never appear. Write a recurrence for $g(n)$. Determine the asymptotic behavior of the recurrence. Also, prove whether this rate of growth is $o(n^{ n^{1/2}}), Theta(n^{ n^{1/2}}),$ or $Omega(n^{ n^{1/2}})$.
My answer:
$g(n)=A(n)+C(n)+G(n)+T(n)$
$g(n)=g(n-1)+g(n-1)+g(n-1)+A(n-1)+C(n-1)$
$g(n)=3g(n-1)+2g(n-2)$
After solving this recurrence, we get
$$begin{align}
g(n) &= (frac{(4)(17)^{1/2}+16}{(3)(17)^{1/2}+17})(frac{3+(17)^{1/2})}{2})^n \
&+(frac{(17)^{1/2}-5)}{2(17)^{1/2}})(frac{3-(17)^{1/2}}{2})^n
end{align}$$
Therefore when $n$ is large, $(frac{3-(17)^{1/2})}{2})^n$ become smaller and smaller
So we can write $$g(n) = Theta((frac{3+(17)^{1/2})}{2})^n).$$
(Do I determine the asymptotic behavior of the recurrence correctly?)
But I do not know what is the rate of growth, if we take the limit of $frac{g(n)}{n^{ n^{1/2}}}$,where n tend to infinity, it seems impossible to calculate it. How could I determine the rate of growth?
discrete-mathematics asymptotics biology
In DNA chain, there are four types of bases: A, C, G, T. Let $g(n)$ be the number of configurations of a DNA chain of length $n$, in which the sequences TT and TG never appear. Write a recurrence for $g(n)$. Determine the asymptotic behavior of the recurrence. Also, prove whether this rate of growth is $o(n^{ n^{1/2}}), Theta(n^{ n^{1/2}}),$ or $Omega(n^{ n^{1/2}})$.
My answer:
$g(n)=A(n)+C(n)+G(n)+T(n)$
$g(n)=g(n-1)+g(n-1)+g(n-1)+A(n-1)+C(n-1)$
$g(n)=3g(n-1)+2g(n-2)$
After solving this recurrence, we get
$$begin{align}
g(n) &= (frac{(4)(17)^{1/2}+16}{(3)(17)^{1/2}+17})(frac{3+(17)^{1/2})}{2})^n \
&+(frac{(17)^{1/2}-5)}{2(17)^{1/2}})(frac{3-(17)^{1/2}}{2})^n
end{align}$$
Therefore when $n$ is large, $(frac{3-(17)^{1/2})}{2})^n$ become smaller and smaller
So we can write $$g(n) = Theta((frac{3+(17)^{1/2})}{2})^n).$$
(Do I determine the asymptotic behavior of the recurrence correctly?)
But I do not know what is the rate of growth, if we take the limit of $frac{g(n)}{n^{ n^{1/2}}}$,where n tend to infinity, it seems impossible to calculate it. How could I determine the rate of growth?
discrete-mathematics asymptotics biology
discrete-mathematics asymptotics biology
edited Nov 26 at 16:06
asked Nov 26 at 15:51
user614642
278
278
Write, for example,$Theta$
for $Theta$; this is what's known as MathJax, a type of $LaTeX$.
– Shaun
Nov 26 at 15:56
Use$frac{a}{b}$
for $frac{a}{b}$.
– Shaun
Nov 26 at 15:58
Please edit the question.
– Shaun
Nov 26 at 15:59
The exercise is strange because it has a much simpler solution. Namely, note that the total number of configurations is $4^n$ hence $g(n)leqslant4^n$. Since $4^n=o(n^{sqrt n})$, you are done.
– Did
Dec 12 at 9:18
add a comment |
Write, for example,$Theta$
for $Theta$; this is what's known as MathJax, a type of $LaTeX$.
– Shaun
Nov 26 at 15:56
Use$frac{a}{b}$
for $frac{a}{b}$.
– Shaun
Nov 26 at 15:58
Please edit the question.
– Shaun
Nov 26 at 15:59
The exercise is strange because it has a much simpler solution. Namely, note that the total number of configurations is $4^n$ hence $g(n)leqslant4^n$. Since $4^n=o(n^{sqrt n})$, you are done.
– Did
Dec 12 at 9:18
Write, for example,
$Theta$
for $Theta$; this is what's known as MathJax, a type of $LaTeX$.– Shaun
Nov 26 at 15:56
Write, for example,
$Theta$
for $Theta$; this is what's known as MathJax, a type of $LaTeX$.– Shaun
Nov 26 at 15:56
Use
$frac{a}{b}$
for $frac{a}{b}$.– Shaun
Nov 26 at 15:58
Use
$frac{a}{b}$
for $frac{a}{b}$.– Shaun
Nov 26 at 15:58
Please edit the question.
– Shaun
Nov 26 at 15:59
Please edit the question.
– Shaun
Nov 26 at 15:59
The exercise is strange because it has a much simpler solution. Namely, note that the total number of configurations is $4^n$ hence $g(n)leqslant4^n$. Since $4^n=o(n^{sqrt n})$, you are done.
– Did
Dec 12 at 9:18
The exercise is strange because it has a much simpler solution. Namely, note that the total number of configurations is $4^n$ hence $g(n)leqslant4^n$. Since $4^n=o(n^{sqrt n})$, you are done.
– Did
Dec 12 at 9:18
add a comment |
1 Answer
1
active
oldest
votes
You solved the recurrence and found its asymptotic behavior correctly. The growth is $c^n$, where $c=frac12(3+sqrt{17})$, and you are asked how this compares with $n^{n^{1/2}}$. The latter is faster: to see this, take logs of both, and note that
$$
(log c)n=oBig(n^{1/2}log nBig)
$$
Thank you very much
– user614642
Nov 27 at 3:53
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%2f3014490%2fasymptotic-behaviour-of-recurrence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
You solved the recurrence and found its asymptotic behavior correctly. The growth is $c^n$, where $c=frac12(3+sqrt{17})$, and you are asked how this compares with $n^{n^{1/2}}$. The latter is faster: to see this, take logs of both, and note that
$$
(log c)n=oBig(n^{1/2}log nBig)
$$
Thank you very much
– user614642
Nov 27 at 3:53
add a comment |
You solved the recurrence and found its asymptotic behavior correctly. The growth is $c^n$, where $c=frac12(3+sqrt{17})$, and you are asked how this compares with $n^{n^{1/2}}$. The latter is faster: to see this, take logs of both, and note that
$$
(log c)n=oBig(n^{1/2}log nBig)
$$
Thank you very much
– user614642
Nov 27 at 3:53
add a comment |
You solved the recurrence and found its asymptotic behavior correctly. The growth is $c^n$, where $c=frac12(3+sqrt{17})$, and you are asked how this compares with $n^{n^{1/2}}$. The latter is faster: to see this, take logs of both, and note that
$$
(log c)n=oBig(n^{1/2}log nBig)
$$
You solved the recurrence and found its asymptotic behavior correctly. The growth is $c^n$, where $c=frac12(3+sqrt{17})$, and you are asked how this compares with $n^{n^{1/2}}$. The latter is faster: to see this, take logs of both, and note that
$$
(log c)n=oBig(n^{1/2}log nBig)
$$
answered Nov 26 at 16:45
Mike Earnest
20.2k11950
20.2k11950
Thank you very much
– user614642
Nov 27 at 3:53
add a comment |
Thank you very much
– user614642
Nov 27 at 3:53
Thank you very much
– user614642
Nov 27 at 3:53
Thank you very much
– user614642
Nov 27 at 3:53
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3014490%2fasymptotic-behaviour-of-recurrence%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
Write, for example,
$Theta$
for $Theta$; this is what's known as MathJax, a type of $LaTeX$.– Shaun
Nov 26 at 15:56
Use
$frac{a}{b}$
for $frac{a}{b}$.– Shaun
Nov 26 at 15:58
Please edit the question.
– Shaun
Nov 26 at 15:59
The exercise is strange because it has a much simpler solution. Namely, note that the total number of configurations is $4^n$ hence $g(n)leqslant4^n$. Since $4^n=o(n^{sqrt n})$, you are done.
– Did
Dec 12 at 9:18