Time complexity of Catalan number
$begingroup$
The below solution is taken from Stack Overflow which has a very large number of
up votes and it was accepted also, but I have a very very small doubt in this.
The solution is the exact copy I didn't change anything. Since the question is very old, no one seems to reply there.
The following function produces the nth number in Catalan numbers. Actually I have doubt regarding the time complexity of this problem.
int catalan(int n)
{
if (n==0 || n==1)
return 1;
int sum = 0;
for(int i=1;i<n;i++)
sum += catalan(i)*catalan(n-i);
return sum;
}
Here is the solution:
My doubt:
Why is it $c(n+1)-c(n)=2+2c(n)$ ? It should be $c(n+1)-c(n)=2c(n)$ because all terms till $c(n-1)$ will be cancelled in line number 6.
To evaluate the complexity, let us focus on the number of recursive calls performed, let $C(n)$.
A call for $n$ implies exactly $2(n-1)$ recursive calls, each of them adding their own costs, $2(C(1)+C(2)+...C(n-1))$.
A call for $n+1$ implies exactly $2n$ recursive calls, each of them adding their own costs, $2(C(1)+C(2)+...C(n-1)+C(n))$.
By difference, $C(n+1)-C(n) = 2+2C(n)$, which can be written $C(n) = 2+3C(n-1)$.
C(1) = 0
C(2) = 2+2C(1) = 2+3C(0) = 2
C(3) = 4+2(C(1)+C(2)) = 2+3C(2) = 8
C(3) = 6+2(C(1)+C(2)+C(3)) = 2+3C(3) = 26
C(4) = 8+2(C(1)+C(2)+C(3)+C(4)) = 2+3C(4) = 80
...
C(n) = 2n-2+2(C(1)+C(2)+...C(n-1)) = 2+3C(n-1)
To solve this recurrence easily, notice that
C(n)+1 = 3(C(n-1)+1) = 9(C(n-2)+1) = ...3^(n-2)(C(2)+1) = 3^(n-1)
Hence, for $n>1$ the exact formula is
C(n) = 3^(n-1)-1
The number of calls to Catalan(1) (constant time), is also $C(n)$, and the numbers of adds or multiplies are $frac{C(n)}{2}$ each.
It is easy to reduce the complexity from $O(3^n)$ to $O(2^n)$ by noting that all terms in the loop (except the middle one) are computed twice - but that still doesn't make it an acceptable implementation :)
discrete-mathematics catalan-numbers
edited Dec 5 '18 at 14:41
Math Girl
633318
asked Dec 5 '18 at 13:55
humblefoolhumblefool
61
$endgroup$
|
show 1 more comment
$begingroup$
The below solution is taken from Stack Overflow which has a very large number of
up votes and it was accepted also, but I have a very very small doubt in this.
The solution is the exact copy I didn't change anything. Since the question is very old, no one seems to reply there.
The following function produces the nth number in Catalan numbers. Actually I have doubt regarding the time complexity of this problem.
int catalan(int n)
{
if (n==0 || n==1)
return 1;
int sum = 0;
for(int i=1;i<n;i++)
sum += catalan(i)*catalan(n-i);
return sum;
}
Here is the solution:
My doubt:
Why is it $c(n+1)-c(n)=2+2c(n)$ ? It should be $c(n+1)-c(n)=2c(n)$ because all terms till $c(n-1)$ will be cancelled in line number 6.
To evaluate the complexity, let us focus on the number of recursive calls performed, let $C(n)$.
A call for $n$ implies exactly $2(n-1)$ recursive calls, each of them adding their own costs, $2(C(1)+C(2)+...C(n-1))$.
A call for $n+1$ implies exactly $2n$ recursive calls, each of them adding their own costs, $2(C(1)+C(2)+...C(n-1)+C(n))$.
By difference, $C(n+1)-C(n) = 2+2C(n)$, which can be written $C(n) = 2+3C(n-1)$.
C(1) = 0
C(2) = 2+2C(1) = 2+3C(0) = 2
C(3) = 4+2(C(1)+C(2)) = 2+3C(2) = 8
C(3) = 6+2(C(1)+C(2)+C(3)) = 2+3C(3) = 26
C(4) = 8+2(C(1)+C(2)+C(3)+C(4)) = 2+3C(4) = 80
...
C(n) = 2n-2+2(C(1)+C(2)+...C(n-1)) = 2+3C(n-1)
To solve this recurrence easily, notice that
C(n)+1 = 3(C(n-1)+1) = 9(C(n-2)+1) = ...3^(n-2)(C(2)+1) = 3^(n-1)
Hence, for $n>1$ the exact formula is
C(n) = 3^(n-1)-1
The number of calls to Catalan(1) (constant time), is also $C(n)$, and the numbers of adds or multiplies are $frac{C(n)}{2}$ each.
It is easy to reduce the complexity from $O(3^n)$ to $O(2^n)$ by noting that all terms in the loop (except the middle one) are computed twice - but that still doesn't make it an acceptable implementation :)
discrete-mathematics catalan-numbers
edited Dec 5 '18 at 14:41
Math Girl
633318
asked Dec 5 '18 at 13:55
humblefoolhumblefool
61
$endgroup$
$begingroup$
What exactly is your question? What is $c(n)$, what is $C(n)$? What is ref [1]?
$endgroup$
– gammatester
Dec 5 '18 at 14:08
$begingroup$
Don't forget the actual calls themselves in addition to the costs internally within the calls. That is to line 3 of the solution you must add the $2(n-1)$ from line 2 and to line 5 add $2n$ from line 4.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 14:11
$begingroup$
The time complexity can be improved to $mathcal{O}(n)$ if each call to $operatorname{catalan}(n)$ is memoized.
$endgroup$
– Alex Vong
Dec 5 '18 at 14:23
1
$begingroup$
@gammatester, the OP's question is in the highlighted "my doubt" paragraph, which refers to a formula a few paragraphs later. Almost everything other than the "my doubt" paragraph is taken verbatim from stackoverflow.com/questions/27371612/… -- including an apparent typo in which $C(3)$ is listed twice, once with the computed value $8$ and again with the computed value $26$. (To the OP: It would help readers here to link to the original; until I found it, it was unclear what you were quoting and what you were saying on your own.)
$endgroup$
– Barry Cipra
Dec 5 '18 at 15:16
$begingroup$
Also, did you leave a comment there asking your "my doubt" question? The answerer, Yves Daoust, is an active participant, at least at MSE.
$endgroup$
– Barry Cipra
Dec 5 '18 at 15:19
|
show 1 more comment
$begingroup$
The below solution is taken from Stack Overflow which has a very large number of
up votes and it was accepted also, but I have a very very small doubt in this.
The solution is the exact copy I didn't change anything. Since the question is very old, no one seems to reply there.
The following function produces the nth number in Catalan numbers. Actually I have doubt regarding the time complexity of this problem.
int catalan(int n)
{
if (n==0 || n==1)
return 1;
int sum = 0;
for(int i=1;i<n;i++)
sum += catalan(i)*catalan(n-i);
return sum;
}
Here is the solution:
My doubt:
Why is it $c(n+1)-c(n)=2+2c(n)$ ? It should be $c(n+1)-c(n)=2c(n)$ because all terms till $c(n-1)$ will be cancelled in line number 6.
To evaluate the complexity, let us focus on the number of recursive calls performed, let $C(n)$.
A call for $n$ implies exactly $2(n-1)$ recursive calls, each of them adding their own costs, $2(C(1)+C(2)+...C(n-1))$.
A call for $n+1$ implies exactly $2n$ recursive calls, each of them adding their own costs, $2(C(1)+C(2)+...C(n-1)+C(n))$.
By difference, $C(n+1)-C(n) = 2+2C(n)$, which can be written $C(n) = 2+3C(n-1)$.
C(1) = 0
C(2) = 2+2C(1) = 2+3C(0) = 2
C(3) = 4+2(C(1)+C(2)) = 2+3C(2) = 8
C(3) = 6+2(C(1)+C(2)+C(3)) = 2+3C(3) = 26
C(4) = 8+2(C(1)+C(2)+C(3)+C(4)) = 2+3C(4) = 80
...
C(n) = 2n-2+2(C(1)+C(2)+...C(n-1)) = 2+3C(n-1)
To solve this recurrence easily, notice that
C(n)+1 = 3(C(n-1)+1) = 9(C(n-2)+1) = ...3^(n-2)(C(2)+1) = 3^(n-1)
Hence, for $n>1$ the exact formula is
C(n) = 3^(n-1)-1
The number of calls to Catalan(1) (constant time), is also $C(n)$, and the numbers of adds or multiplies are $frac{C(n)}{2}$ each.
It is easy to reduce the complexity from $O(3^n)$ to $O(2^n)$ by noting that all terms in the loop (except the middle one) are computed twice - but that still doesn't make it an acceptable implementation :)
discrete-mathematics catalan-numbers
edited Dec 5 '18 at 14:41
Math Girl
633318
asked Dec 5 '18 at 13:55
humblefoolhumblefool
61
$endgroup$
The below solution is taken from Stack Overflow which has a very large number of
up votes and it was accepted also, but I have a very very small doubt in this.
The solution is the exact copy I didn't change anything. Since the question is very old, no one seems to reply there.
The following function produces the nth number in Catalan numbers. Actually I have doubt regarding the time complexity of this problem.
int catalan(int n)
{
if (n==0 || n==1)
return 1;
int sum = 0;
for(int i=1;i<n;i++)
sum += catalan(i)*catalan(n-i);
return sum;
}
Here is the solution:
My doubt:
Why is it $c(n+1)-c(n)=2+2c(n)$ ? It should be $c(n+1)-c(n)=2c(n)$ because all terms till $c(n-1)$ will be cancelled in line number 6.
To evaluate the complexity, let us focus on the number of recursive calls performed, let $C(n)$.
A call for $n$ implies exactly $2(n-1)$ recursive calls, each of them adding their own costs, $2(C(1)+C(2)+...C(n-1))$.
A call for $n+1$ implies exactly $2n$ recursive calls, each of them adding their own costs, $2(C(1)+C(2)+...C(n-1)+C(n))$.
By difference, $C(n+1)-C(n) = 2+2C(n)$, which can be written $C(n) = 2+3C(n-1)$.
C(1) = 0
C(2) = 2+2C(1) = 2+3C(0) = 2
C(3) = 4+2(C(1)+C(2)) = 2+3C(2) = 8
C(3) = 6+2(C(1)+C(2)+C(3)) = 2+3C(3) = 26
C(4) = 8+2(C(1)+C(2)+C(3)+C(4)) = 2+3C(4) = 80
...
C(n) = 2n-2+2(C(1)+C(2)+...C(n-1)) = 2+3C(n-1)
To solve this recurrence easily, notice that
C(n)+1 = 3(C(n-1)+1) = 9(C(n-2)+1) = ...3^(n-2)(C(2)+1) = 3^(n-1)
Hence, for $n>1$ the exact formula is
C(n) = 3^(n-1)-1
The number of calls to Catalan(1) (constant time), is also $C(n)$, and the numbers of adds or multiplies are $frac{C(n)}{2}$ each.
It is easy to reduce the complexity from $O(3^n)$ to $O(2^n)$ by noting that all terms in the loop (except the middle one) are computed twice - but that still doesn't make it an acceptable implementation :)
discrete-mathematics catalan-numbers
discrete-mathematics catalan-numbers
edited Dec 5 '18 at 14:41
Math Girl
633318
asked Dec 5 '18 at 13:55
humblefoolhumblefool
61
edited Dec 5 '18 at 14:41
Math Girl
633318
asked Dec 5 '18 at 13:55
humblefoolhumblefool
61
edited Dec 5 '18 at 14:41
Math Girl
633318
edited Dec 5 '18 at 14:41
Math Girl
633318
edited Dec 5 '18 at 14:41
Math Girl
633318
633318
asked Dec 5 '18 at 13:55
humblefoolhumblefool
61
asked Dec 5 '18 at 13:55
humblefoolhumblefool
61
asked Dec 5 '18 at 13:55
humblefoolhumblefool
61
61
$begingroup$
What exactly is your question? What is $c(n)$, what is $C(n)$? What is ref [1]?
$endgroup$
– gammatester
Dec 5 '18 at 14:08
$begingroup$
Don't forget the actual calls themselves in addition to the costs internally within the calls. That is to line 3 of the solution you must add the $2(n-1)$ from line 2 and to line 5 add $2n$ from line 4.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 14:11
$begingroup$
The time complexity can be improved to $mathcal{O}(n)$ if each call to $operatorname{catalan}(n)$ is memoized.
$endgroup$
– Alex Vong
Dec 5 '18 at 14:23
1
$begingroup$
@gammatester, the OP's question is in the highlighted "my doubt" paragraph, which refers to a formula a few paragraphs later. Almost everything other than the "my doubt" paragraph is taken verbatim from stackoverflow.com/questions/27371612/… -- including an apparent typo in which $C(3)$ is listed twice, once with the computed value $8$ and again with the computed value $26$. (To the OP: It would help readers here to link to the original; until I found it, it was unclear what you were quoting and what you were saying on your own.)
$endgroup$
– Barry Cipra
Dec 5 '18 at 15:16
$begingroup$
Also, did you leave a comment there asking your "my doubt" question? The answerer, Yves Daoust, is an active participant, at least at MSE.
$endgroup$
– Barry Cipra
Dec 5 '18 at 15:19
|
show 1 more comment
$begingroup$
What exactly is your question? What is $c(n)$, what is $C(n)$? What is ref [1]?
$endgroup$
– gammatester
Dec 5 '18 at 14:08
$begingroup$
Don't forget the actual calls themselves in addition to the costs internally within the calls. That is to line 3 of the solution you must add the $2(n-1)$ from line 2 and to line 5 add $2n$ from line 4.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 14:11
$begingroup$
The time complexity can be improved to $mathcal{O}(n)$ if each call to $operatorname{catalan}(n)$ is memoized.
$endgroup$
– Alex Vong
Dec 5 '18 at 14:23
1
$begingroup$
@gammatester, the OP's question is in the highlighted "my doubt" paragraph, which refers to a formula a few paragraphs later. Almost everything other than the "my doubt" paragraph is taken verbatim from stackoverflow.com/questions/27371612/… -- including an apparent typo in which $C(3)$ is listed twice, once with the computed value $8$ and again with the computed value $26$. (To the OP: It would help readers here to link to the original; until I found it, it was unclear what you were quoting and what you were saying on your own.)
$endgroup$
– Barry Cipra
Dec 5 '18 at 15:16
$begingroup$
Also, did you leave a comment there asking your "my doubt" question? The answerer, Yves Daoust, is an active participant, at least at MSE.
$endgroup$
– Barry Cipra
Dec 5 '18 at 15:19
$begingroup$
What exactly is your question? What is $c(n)$, what is $C(n)$? What is ref [1]?
$endgroup$
– gammatester
Dec 5 '18 at 14:08
$begingroup$
What exactly is your question? What is $c(n)$, what is $C(n)$? What is ref [1]?
$endgroup$
– gammatester
Dec 5 '18 at 14:08
$begingroup$
Don't forget the actual calls themselves in addition to the costs internally within the calls. That is to line 3 of the solution you must add the $2(n-1)$ from line 2 and to line 5 add $2n$ from line 4.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 14:11
$begingroup$
Don't forget the actual calls themselves in addition to the costs internally within the calls. That is to line 3 of the solution you must add the $2(n-1)$ from line 2 and to line 5 add $2n$ from line 4.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 14:11
$begingroup$
The time complexity can be improved to $mathcal{O}(n)$ if each call to $operatorname{catalan}(n)$ is memoized.
$endgroup$
– Alex Vong
Dec 5 '18 at 14:23
$begingroup$
The time complexity can be improved to $mathcal{O}(n)$ if each call to $operatorname{catalan}(n)$ is memoized.
$endgroup$
– Alex Vong
Dec 5 '18 at 14:23
1
1
$begingroup$
@gammatester, the OP's question is in the highlighted "my doubt" paragraph, which refers to a formula a few paragraphs later. Almost everything other than the "my doubt" paragraph is taken verbatim from stackoverflow.com/questions/27371612/… -- including an apparent typo in which $C(3)$ is listed twice, once with the computed value $8$ and again with the computed value $26$. (To the OP: It would help readers here to link to the original; until I found it, it was unclear what you were quoting and what you were saying on your own.)
$endgroup$
– Barry Cipra
Dec 5 '18 at 15:16
$begingroup$
@gammatester, the OP's question is in the highlighted "my doubt" paragraph, which refers to a formula a few paragraphs later. Almost everything other than the "my doubt" paragraph is taken verbatim from stackoverflow.com/questions/27371612/… -- including an apparent typo in which $C(3)$ is listed twice, once with the computed value $8$ and again with the computed value $26$. (To the OP: It would help readers here to link to the original; until I found it, it was unclear what you were quoting and what you were saying on your own.)
$endgroup$
– Barry Cipra
Dec 5 '18 at 15:16
$begingroup$
Also, did you leave a comment there asking your "my doubt" question? The answerer, Yves Daoust, is an active participant, at least at MSE.
$endgroup$
– Barry Cipra
Dec 5 '18 at 15:19
$begingroup$
Also, did you leave a comment there asking your "my doubt" question? The answerer, Yves Daoust, is an active participant, at least at MSE.
$endgroup$
– Barry Cipra
Dec 5 '18 at 15:19
|
show 1 more comment
0
active
oldest
votes
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%2f3027091%2ftime-complexity-of-catalan-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3027091%2ftime-complexity-of-catalan-number%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$
What exactly is your question? What is $c(n)$, what is $C(n)$? What is ref [1]?
$endgroup$
– gammatester
Dec 5 '18 at 14:08
$begingroup$
Don't forget the actual calls themselves in addition to the costs internally within the calls. That is to line 3 of the solution you must add the $2(n-1)$ from line 2 and to line 5 add $2n$ from line 4.
$endgroup$
– Michal Adamaszek
Dec 5 '18 at 14:11
$begingroup$
The time complexity can be improved to $mathcal{O}(n)$ if each call to $operatorname{catalan}(n)$ is memoized.
$endgroup$
– Alex Vong
Dec 5 '18 at 14:23
1
$begingroup$
@gammatester, the OP's question is in the highlighted "my doubt" paragraph, which refers to a formula a few paragraphs later. Almost everything other than the "my doubt" paragraph is taken verbatim from stackoverflow.com/questions/27371612/… -- including an apparent typo in which $C(3)$ is listed twice, once with the computed value $8$ and again with the computed value $26$. (To the OP: It would help readers here to link to the original; until I found it, it was unclear what you were quoting and what you were saying on your own.)
$endgroup$
– Barry Cipra
Dec 5 '18 at 15:16
$begingroup$
Also, did you leave a comment there asking your "my doubt" question? The answerer, Yves Daoust, is an active participant, at least at MSE.
$endgroup$
– Barry Cipra
Dec 5 '18 at 15:19