Mixing
Recursive Relation $T(n)=T(n-1)+1$
-2
$begingroup$
I have wrote a recursive code of the type:
function(n){
if n==1:
return
else{
do something
function(n-1)
}
Now I am trying to analyze the complexity
I came to $T(n)=T(n-1)+1$ but how do I solve this kind of recursive relation? master theorem can not be used, I vaguely remember something like:
$$T(n)=T(n-1)+1$$
$$T(n-1)=T(n-2)+1$$
$$T(n-2)=T(n-3)+1$$
So it is of the kind
$$T(n)=T(n-k)+1$$
and then we set $m=n-k$
But I do not remember how to proceed.
recurrence-relations recursion
edited Jan 31 at 20:52
Bernard
124k741117
asked Jan 31 at 20:48
gboxgbox
5,50062364
$endgroup$
add a comment |
-2
$begingroup$
I have wrote a recursive code of the type:
function(n){
if n==1:
return
else{
do something
function(n-1)
}
Now I am trying to analyze the complexity
I came to $T(n)=T(n-1)+1$ but how do I solve this kind of recursive relation? master theorem can not be used, I vaguely remember something like:
$$T(n)=T(n-1)+1$$
$$T(n-1)=T(n-2)+1$$
$$T(n-2)=T(n-3)+1$$
So it is of the kind
$$T(n)=T(n-k)+1$$
and then we set $m=n-k$
But I do not remember how to proceed.
recurrence-relations recursion
edited Jan 31 at 20:52
Bernard
124k741117
asked Jan 31 at 20:48
gboxgbox
5,50062364
$endgroup$
1
$begingroup$
It should $T(n)=T(n-k)+k$. This is an arithmetic progression.
$endgroup$
– Bernard
Jan 31 at 20:51
$begingroup$
Your analysis is only correct if the time complexity of "$mathtt{do ;something}$" is independent of $n$. If that is the case, then the sum of the arithmetic progression is easily found by thinking about counting on your fingers.
$endgroup$
– Rob Arthan
Jan 31 at 21:06
$begingroup$
@Bernard yes that what I meant, the next step it substitution of $n-k$ or something like that, where can I read more about this subject?
$endgroup$
– gbox
Feb 1 at 10:01
$begingroup$
You can take a look at Wikipedia for instance.
$endgroup$
– Bernard
Feb 1 at 10:41
add a comment |
-2
-2
-2
$begingroup$
I have wrote a recursive code of the type:
function(n){
if n==1:
return
else{
do something
function(n-1)
}
Now I am trying to analyze the complexity
I came to $T(n)=T(n-1)+1$ but how do I solve this kind of recursive relation? master theorem can not be used, I vaguely remember something like:
$$T(n)=T(n-1)+1$$
$$T(n-1)=T(n-2)+1$$
$$T(n-2)=T(n-3)+1$$
So it is of the kind
$$T(n)=T(n-k)+1$$
and then we set $m=n-k$
But I do not remember how to proceed.
recurrence-relations recursion
edited Jan 31 at 20:52
Bernard
124k741117
asked Jan 31 at 20:48
gboxgbox
5,50062364
$endgroup$
I have wrote a recursive code of the type:
function(n){
if n==1:
return
else{
do something
function(n-1)
}
Now I am trying to analyze the complexity
I came to $T(n)=T(n-1)+1$ but how do I solve this kind of recursive relation? master theorem can not be used, I vaguely remember something like:
$$T(n)=T(n-1)+1$$
$$T(n-1)=T(n-2)+1$$
$$T(n-2)=T(n-3)+1$$
So it is of the kind
$$T(n)=T(n-k)+1$$
and then we set $m=n-k$
But I do not remember how to proceed.
recurrence-relations recursion
recurrence-relations recursion
edited Jan 31 at 20:52
Bernard
124k741117
asked Jan 31 at 20:48
gboxgbox
5,50062364
edited Jan 31 at 20:52
Bernard
124k741117
asked Jan 31 at 20:48
gboxgbox
5,50062364
edited Jan 31 at 20:52
Bernard
124k741117
edited Jan 31 at 20:52
Bernard
124k741117
edited Jan 31 at 20:52
Bernard
124k741117
124k741117
asked Jan 31 at 20:48
gboxgbox
5,50062364
asked Jan 31 at 20:48
gboxgbox
5,50062364
asked Jan 31 at 20:48
gboxgbox
5,50062364
5,50062364
1
$begingroup$
It should $T(n)=T(n-k)+k$. This is an arithmetic progression.
$endgroup$
– Bernard
Jan 31 at 20:51
$begingroup$
Your analysis is only correct if the time complexity of "$mathtt{do ;something}$" is independent of $n$. If that is the case, then the sum of the arithmetic progression is easily found by thinking about counting on your fingers.
$endgroup$
– Rob Arthan
Jan 31 at 21:06
$begingroup$
@Bernard yes that what I meant, the next step it substitution of $n-k$ or something like that, where can I read more about this subject?
$endgroup$
– gbox
Feb 1 at 10:01
$begingroup$
You can take a look at Wikipedia for instance.
$endgroup$
– Bernard
Feb 1 at 10:41
add a comment |
1
$begingroup$
It should $T(n)=T(n-k)+k$. This is an arithmetic progression.
$endgroup$
– Bernard
Jan 31 at 20:51
$begingroup$
Your analysis is only correct if the time complexity of "$mathtt{do ;something}$" is independent of $n$. If that is the case, then the sum of the arithmetic progression is easily found by thinking about counting on your fingers.
$endgroup$
– Rob Arthan
Jan 31 at 21:06
$begingroup$
@Bernard yes that what I meant, the next step it substitution of $n-k$ or something like that, where can I read more about this subject?
$endgroup$
– gbox
Feb 1 at 10:01
$begingroup$
You can take a look at Wikipedia for instance.
$endgroup$
– Bernard
Feb 1 at 10:41
1
1
$begingroup$
It should $T(n)=T(n-k)+k$. This is an arithmetic progression.
$endgroup$
– Bernard
Jan 31 at 20:51
$begingroup$
It should $T(n)=T(n-k)+k$. This is an arithmetic progression.
$endgroup$
– Bernard
Jan 31 at 20:51
$begingroup$
Your analysis is only correct if the time complexity of "$mathtt{do ;something}$" is independent of $n$. If that is the case, then the sum of the arithmetic progression is easily found by thinking about counting on your fingers.
$endgroup$
– Rob Arthan
Jan 31 at 21:06
$begingroup$
Your analysis is only correct if the time complexity of "$mathtt{do ;something}$" is independent of $n$. If that is the case, then the sum of the arithmetic progression is easily found by thinking about counting on your fingers.
$endgroup$
– Rob Arthan
Jan 31 at 21:06
$begingroup$
@Bernard yes that what I meant, the next step it substitution of $n-k$ or something like that, where can I read more about this subject?
$endgroup$
– gbox
Feb 1 at 10:01
$begingroup$
@Bernard yes that what I meant, the next step it substitution of $n-k$ or something like that, where can I read more about this subject?
$endgroup$
– gbox
Feb 1 at 10:01
$begingroup$
You can take a look at Wikipedia for instance.
$endgroup$
– Bernard
Feb 1 at 10:41
$begingroup$
You can take a look at Wikipedia for instance.
$endgroup$
– Bernard
Feb 1 at 10:41
add a comment |
2 Answers
2
active
oldest
votes
2
$begingroup$
Note this
$$T(n) - T(0) = sum_{k=1}^n T(k) - T(k-1).$$
answered Jan 31 at 20:51
ncmathsadistncmathsadist
43.1k261103
$endgroup$
$begingroup$
Multiplying this by $frac{n}{2}$ will give use the sum of the arithmetic progression so $frac{n(T(n)-1)}{2}=sum_{k=1}^{n}frac{n(T(k)-T(k-1)}{2}$ we want to find an expression for $T(n)$ which is not recursive?
$endgroup$
– gbox
Feb 1 at 10:02
add a comment |
2
$begingroup$
By expanding the recursive equation, you can found $T(n) = Theta(n)$ (by induction).
answered Jan 31 at 20:53
OmGOmG
2,5371824
$endgroup$
$begingroup$
If I look at $T(n)-T(n-1)=n$ and then summing it, I get $T(n)-1=frac{n(n+1)}{2}$ or $T(n)=frac{n(n+1)}{2}+1$ how is it $Theta (n)$?
$endgroup$
– gbox
Feb 1 at 10:16
1
$begingroup$
@gbox Sorry, you are wrong. $T(n) - T(n-1) = 1$ by your definition.
$endgroup$
– OmG
Feb 1 at 11:56
$begingroup$
Sorry, you are correct so the sum of $sum T(n)-T(n-1)=T(n)-T(0)=n$
$endgroup$
– gbox
Feb 1 at 13:28
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
});
}
});
draft saved
draft discarded
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%2f3095432%2frecursive-relation-tn-tn-11%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
2
$begingroup$
Note this
$$T(n) - T(0) = sum_{k=1}^n T(k) - T(k-1).$$
answered Jan 31 at 20:51
ncmathsadistncmathsadist
43.1k261103
$endgroup$
$begingroup$
Multiplying this by $frac{n}{2}$ will give use the sum of the arithmetic progression so $frac{n(T(n)-1)}{2}=sum_{k=1}^{n}frac{n(T(k)-T(k-1)}{2}$ we want to find an expression for $T(n)$ which is not recursive?
$endgroup$
– gbox
Feb 1 at 10:02
add a comment |
2
$begingroup$
Note this
$$T(n) - T(0) = sum_{k=1}^n T(k) - T(k-1).$$
answered Jan 31 at 20:51
ncmathsadistncmathsadist
43.1k261103
$endgroup$
$begingroup$
Multiplying this by $frac{n}{2}$ will give use the sum of the arithmetic progression so $frac{n(T(n)-1)}{2}=sum_{k=1}^{n}frac{n(T(k)-T(k-1)}{2}$ we want to find an expression for $T(n)$ which is not recursive?
$endgroup$
– gbox
Feb 1 at 10:02
add a comment |
2
2
2
$begingroup$
Note this
$$T(n) - T(0) = sum_{k=1}^n T(k) - T(k-1).$$
answered Jan 31 at 20:51
ncmathsadistncmathsadist
43.1k261103
$endgroup$
Note this
$$T(n) - T(0) = sum_{k=1}^n T(k) - T(k-1).$$
answered Jan 31 at 20:51
ncmathsadistncmathsadist
43.1k261103
answered Jan 31 at 20:51
ncmathsadistncmathsadist
43.1k261103
answered Jan 31 at 20:51
ncmathsadistncmathsadist
43.1k261103
answered Jan 31 at 20:51
ncmathsadistncmathsadist
43.1k261103
43.1k261103
$begingroup$
Multiplying this by $frac{n}{2}$ will give use the sum of the arithmetic progression so $frac{n(T(n)-1)}{2}=sum_{k=1}^{n}frac{n(T(k)-T(k-1)}{2}$ we want to find an expression for $T(n)$ which is not recursive?
$endgroup$
– gbox
Feb 1 at 10:02
add a comment |
$begingroup$
Multiplying this by $frac{n}{2}$ will give use the sum of the arithmetic progression so $frac{n(T(n)-1)}{2}=sum_{k=1}^{n}frac{n(T(k)-T(k-1)}{2}$ we want to find an expression for $T(n)$ which is not recursive?
$endgroup$
– gbox
Feb 1 at 10:02
$begingroup$
Multiplying this by $frac{n}{2}$ will give use the sum of the arithmetic progression so $frac{n(T(n)-1)}{2}=sum_{k=1}^{n}frac{n(T(k)-T(k-1)}{2}$ we want to find an expression for $T(n)$ which is not recursive?
$endgroup$
– gbox
Feb 1 at 10:02
$begingroup$
Multiplying this by $frac{n}{2}$ will give use the sum of the arithmetic progression so $frac{n(T(n)-1)}{2}=sum_{k=1}^{n}frac{n(T(k)-T(k-1)}{2}$ we want to find an expression for $T(n)$ which is not recursive?
$endgroup$
– gbox
Feb 1 at 10:02
add a comment |
2
$begingroup$
By expanding the recursive equation, you can found $T(n) = Theta(n)$ (by induction).
answered Jan 31 at 20:53
OmGOmG
2,5371824
$endgroup$
$begingroup$
If I look at $T(n)-T(n-1)=n$ and then summing it, I get $T(n)-1=frac{n(n+1)}{2}$ or $T(n)=frac{n(n+1)}{2}+1$ how is it $Theta (n)$?
$endgroup$
– gbox
Feb 1 at 10:16
1
$begingroup$
@gbox Sorry, you are wrong. $T(n) - T(n-1) = 1$ by your definition.
$endgroup$
– OmG
Feb 1 at 11:56
$begingroup$
Sorry, you are correct so the sum of $sum T(n)-T(n-1)=T(n)-T(0)=n$
$endgroup$
– gbox
Feb 1 at 13:28
add a comment |
2
$begingroup$
By expanding the recursive equation, you can found $T(n) = Theta(n)$ (by induction).
answered Jan 31 at 20:53
OmGOmG
2,5371824
$endgroup$
$begingroup$
If I look at $T(n)-T(n-1)=n$ and then summing it, I get $T(n)-1=frac{n(n+1)}{2}$ or $T(n)=frac{n(n+1)}{2}+1$ how is it $Theta (n)$?
$endgroup$
– gbox
Feb 1 at 10:16
1
$begingroup$
@gbox Sorry, you are wrong. $T(n) - T(n-1) = 1$ by your definition.
$endgroup$
– OmG
Feb 1 at 11:56
$begingroup$
Sorry, you are correct so the sum of $sum T(n)-T(n-1)=T(n)-T(0)=n$
$endgroup$
– gbox
Feb 1 at 13:28
add a comment |
2
2
2
$begingroup$
By expanding the recursive equation, you can found $T(n) = Theta(n)$ (by induction).
answered Jan 31 at 20:53
OmGOmG
2,5371824
$endgroup$
By expanding the recursive equation, you can found $T(n) = Theta(n)$ (by induction).
answered Jan 31 at 20:53
OmGOmG
2,5371824
answered Jan 31 at 20:53
OmGOmG
2,5371824
answered Jan 31 at 20:53
OmGOmG
2,5371824
answered Jan 31 at 20:53
OmGOmG
2,5371824
2,5371824
$begingroup$
If I look at $T(n)-T(n-1)=n$ and then summing it, I get $T(n)-1=frac{n(n+1)}{2}$ or $T(n)=frac{n(n+1)}{2}+1$ how is it $Theta (n)$?
$endgroup$
– gbox
Feb 1 at 10:16
1
$begingroup$
@gbox Sorry, you are wrong. $T(n) - T(n-1) = 1$ by your definition.
$endgroup$
– OmG
Feb 1 at 11:56
$begingroup$
Sorry, you are correct so the sum of $sum T(n)-T(n-1)=T(n)-T(0)=n$
$endgroup$
– gbox
Feb 1 at 13:28
add a comment |
$begingroup$
If I look at $T(n)-T(n-1)=n$ and then summing it, I get $T(n)-1=frac{n(n+1)}{2}$ or $T(n)=frac{n(n+1)}{2}+1$ how is it $Theta (n)$?
$endgroup$
– gbox
Feb 1 at 10:16
1
$begingroup$
@gbox Sorry, you are wrong. $T(n) - T(n-1) = 1$ by your definition.
$endgroup$
– OmG
Feb 1 at 11:56
$begingroup$
Sorry, you are correct so the sum of $sum T(n)-T(n-1)=T(n)-T(0)=n$
$endgroup$
– gbox
Feb 1 at 13:28
$begingroup$
If I look at $T(n)-T(n-1)=n$ and then summing it, I get $T(n)-1=frac{n(n+1)}{2}$ or $T(n)=frac{n(n+1)}{2}+1$ how is it $Theta (n)$?
$endgroup$
– gbox
Feb 1 at 10:16
$begingroup$
If I look at $T(n)-T(n-1)=n$ and then summing it, I get $T(n)-1=frac{n(n+1)}{2}$ or $T(n)=frac{n(n+1)}{2}+1$ how is it $Theta (n)$?
$endgroup$
– gbox
Feb 1 at 10:16
1
1
$begingroup$
@gbox Sorry, you are wrong. $T(n) - T(n-1) = 1$ by your definition.
$endgroup$
– OmG
Feb 1 at 11:56
$begingroup$
@gbox Sorry, you are wrong. $T(n) - T(n-1) = 1$ by your definition.
$endgroup$
– OmG
Feb 1 at 11:56
$begingroup$
Sorry, you are correct so the sum of $sum T(n)-T(n-1)=T(n)-T(0)=n$
$endgroup$
– gbox
Feb 1 at 13:28
$begingroup$
Sorry, you are correct so the sum of $sum T(n)-T(n-1)=T(n)-T(0)=n$
$endgroup$
– gbox
Feb 1 at 13:28
add a comment |
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f3095432%2frecursive-relation-tn-tn-11%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
1
$begingroup$
It should $T(n)=T(n-k)+k$. This is an arithmetic progression.
$endgroup$
– Bernard
Jan 31 at 20:51
$begingroup$
Your analysis is only correct if the time complexity of "$mathtt{do ;something}$" is independent of $n$. If that is the case, then the sum of the arithmetic progression is easily found by thinking about counting on your fingers.
$endgroup$
– Rob Arthan
Jan 31 at 21:06
$begingroup$
@Bernard yes that what I meant, the next step it substitution of $n-k$ or something like that, where can I read more about this subject?
$endgroup$
– gbox
Feb 1 at 10:01
$begingroup$
You can take a look at Wikipedia for instance.
$endgroup$
– Bernard
Feb 1 at 10:41