Understanding the recurrence relation T(n) = c(T(n/c) + 1) Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Second Order Homogeneous Recurrence Relation QuestionLinear Homogeneous Recurrence Relations and Inhomogenous Recurrence RelationsUnderstanding non homogeneous recurrenceWhat is the intuitive idea behind looking for a solution of the form an=r^n for a linear homogeneous recurrence relation?Finding particular solution when solving recurrence relationRecurrence relation. Why subtitute $A_n = cr^n$ for second order homogeneous recurrence?recurrence relation function definitiongeneral solution for a recurrence relationSolving the recurrence relation $y_n+1=y_n+a+fracby_n$Solving Recurrence Relation Using Substitution/Geometric Series
Single author papers against my advisor's will?
Why is "Captain Marvel" translated as male in Portugal?
What can I do if my MacBook isn’t charging but already ran out?
Estimate capacitor parameters
Using "nakedly" instead of "with nothing on"
What was the last x86 CPU that did not have the x87 floating-point unit built in?
Direct Experience of Meditation
What is the largest species of polychaete?
Cauchy Sequence Characterized only By Directly Neighbouring Sequence Members
Can a zero nonce be safely used with AES-GCM if the key is random and never used again?
How do I keep my slimes from escaping their pens?
When is phishing education going too far?
Unexpected result with right shift after bitwise negation
Why does tar appear to skip file contents when output file is /dev/null?
Blender game recording at the wrong time
Complexity of many constant time steps with occasional logarithmic steps
Need a suitable toxic chemical for a murder plot in my novel
What is the order of Mitzvot in Rambam's Sefer Hamitzvot?
Mortgage adviser recommends a longer term than necessary combined with overpayments
How do I automatically answer y in bash script?
3 doors, three guards, one stone
Area of a 2D convex hull
What items from the Roman-age tech-level could be used to deter all creatures from entering a small area?
How do you clear the ApexPages.getMessages() collection in a test?
Understanding the recurrence relation T(n) = c(T(n/c) + 1)
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Second Order Homogeneous Recurrence Relation QuestionLinear Homogeneous Recurrence Relations and Inhomogenous Recurrence RelationsUnderstanding non homogeneous recurrenceWhat is the intuitive idea behind looking for a solution of the form an=r^n for a linear homogeneous recurrence relation?Finding particular solution when solving recurrence relationRecurrence relation. Why subtitute $A_n = cr^n$ for second order homogeneous recurrence?recurrence relation function definitiongeneral solution for a recurrence relationSolving the recurrence relation $y_n+1=y_n+a+fracby_n$Solving Recurrence Relation Using Substitution/Geometric Series
$begingroup$
Solve the recurrence relation T(n) = c(T(n/c) + 1), T(1) = 1, by finding an expression for T(n) in big-Oh notation.
Think about inputs of the form $c^k$.
$$T(c^k)=cT(c^k-1)+c=c^2T(c^k-2)+c^2+c=;...=
> c^kT(1)+c+c^2+c^3+...+c^k$$ $$T(c^k)=fracccdot
> c^k-1c-1+c^kT(1)$$
If we want this function to be continuous, we note that
$$T(n)=T(c^log_cn)=fraccn-1c-1+T(1)n$$
If we let $a=T(1)+frac 1c-1$ be an arbitrary constant, we get
$$T(n)=an-frac1c-1$$
This is the general form of the recursion. To find the specific form
given your constraint, we substitute $T(1)=1$ into our equation for
$a$, getting $a=1+frac 1c-1=frac cc-1$. So, the final solution
is $$T(n)=fracccdot n-1c-1$$
And, this function has complexity of $O(n)$ as it is a linear
function.
So this is a question that has been answered, but this post in particular is look for alternative methods, or an explanation for the solution that I already got.
The following solution by Don Thousand does a great job of going through the steps, but I'm a beginner at this and I don't understand the process or reasoning behind a lot of the work, and was hoping someone could help me understand this method, or possibly provide an alternative.
discrete-mathematics recurrence-relations computer-science
asked Apr 8 at 20:31
BrownieBrownie
3327
$endgroup$
add a comment |
$begingroup$
Solve the recurrence relation T(n) = c(T(n/c) + 1), T(1) = 1, by finding an expression for T(n) in big-Oh notation.
Think about inputs of the form $c^k$.
$$T(c^k)=cT(c^k-1)+c=c^2T(c^k-2)+c^2+c=;...=
> c^kT(1)+c+c^2+c^3+...+c^k$$ $$T(c^k)=fracccdot
> c^k-1c-1+c^kT(1)$$
If we want this function to be continuous, we note that
$$T(n)=T(c^log_cn)=fraccn-1c-1+T(1)n$$
If we let $a=T(1)+frac 1c-1$ be an arbitrary constant, we get
$$T(n)=an-frac1c-1$$
This is the general form of the recursion. To find the specific form
given your constraint, we substitute $T(1)=1$ into our equation for
$a$, getting $a=1+frac 1c-1=frac cc-1$. So, the final solution
is $$T(n)=fracccdot n-1c-1$$
And, this function has complexity of $O(n)$ as it is a linear
function.
So this is a question that has been answered, but this post in particular is look for alternative methods, or an explanation for the solution that I already got.
The following solution by Don Thousand does a great job of going through the steps, but I'm a beginner at this and I don't understand the process or reasoning behind a lot of the work, and was hoping someone could help me understand this method, or possibly provide an alternative.
discrete-mathematics recurrence-relations computer-science
asked Apr 8 at 20:31
BrownieBrownie
3327
$endgroup$
add a comment |
$begingroup$
Solve the recurrence relation T(n) = c(T(n/c) + 1), T(1) = 1, by finding an expression for T(n) in big-Oh notation.
Think about inputs of the form $c^k$.
$$T(c^k)=cT(c^k-1)+c=c^2T(c^k-2)+c^2+c=;...=
> c^kT(1)+c+c^2+c^3+...+c^k$$ $$T(c^k)=fracccdot
> c^k-1c-1+c^kT(1)$$
If we want this function to be continuous, we note that
$$T(n)=T(c^log_cn)=fraccn-1c-1+T(1)n$$
If we let $a=T(1)+frac 1c-1$ be an arbitrary constant, we get
$$T(n)=an-frac1c-1$$
This is the general form of the recursion. To find the specific form
given your constraint, we substitute $T(1)=1$ into our equation for
$a$, getting $a=1+frac 1c-1=frac cc-1$. So, the final solution
is $$T(n)=fracccdot n-1c-1$$
And, this function has complexity of $O(n)$ as it is a linear
function.
So this is a question that has been answered, but this post in particular is look for alternative methods, or an explanation for the solution that I already got.
The following solution by Don Thousand does a great job of going through the steps, but I'm a beginner at this and I don't understand the process or reasoning behind a lot of the work, and was hoping someone could help me understand this method, or possibly provide an alternative.
discrete-mathematics recurrence-relations computer-science
asked Apr 8 at 20:31
BrownieBrownie
3327
$endgroup$
Solve the recurrence relation T(n) = c(T(n/c) + 1), T(1) = 1, by finding an expression for T(n) in big-Oh notation.
Think about inputs of the form $c^k$.
$$T(c^k)=cT(c^k-1)+c=c^2T(c^k-2)+c^2+c=;...=
> c^kT(1)+c+c^2+c^3+...+c^k$$ $$T(c^k)=fracccdot
> c^k-1c-1+c^kT(1)$$
If we want this function to be continuous, we note that
$$T(n)=T(c^log_cn)=fraccn-1c-1+T(1)n$$
If we let $a=T(1)+frac 1c-1$ be an arbitrary constant, we get
$$T(n)=an-frac1c-1$$
This is the general form of the recursion. To find the specific form
given your constraint, we substitute $T(1)=1$ into our equation for
$a$, getting $a=1+frac 1c-1=frac cc-1$. So, the final solution
is $$T(n)=fracccdot n-1c-1$$
And, this function has complexity of $O(n)$ as it is a linear
function.
So this is a question that has been answered, but this post in particular is look for alternative methods, or an explanation for the solution that I already got.
The following solution by Don Thousand does a great job of going through the steps, but I'm a beginner at this and I don't understand the process or reasoning behind a lot of the work, and was hoping someone could help me understand this method, or possibly provide an alternative.
discrete-mathematics recurrence-relations computer-science
discrete-mathematics recurrence-relations computer-science
asked Apr 8 at 20:31
BrownieBrownie
3327
asked Apr 8 at 20:31
BrownieBrownie
3327
asked Apr 8 at 20:31
BrownieBrownie
3327
asked Apr 8 at 20:31
BrownieBrownie
3327
asked Apr 8 at 20:31
BrownieBrownie
3327
3327
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Assume a linear ansatz of $ T(n) := a n + b. $
The recursion equation we now have is
$$ T(n) = a n + b = c(T(n/c) + 1) = c( a n/c + b+1) = a n + b c + c. $$
Solve this equation to get $ b = -c/(c-1). $ Thus we have
$ T(n) = a n - c/(c-1) $ and $ T(n) = O(n) $ as we expected.
We need to find $ a $ using $ T(1)=1 $ with solution
$ a = (2c-1)/(c-1). $ Finally, $ T(n) = ((2c-1)n-c)/(c-1).$
The key to this solution is the ansatz which was a guess. It worked, but in general, it would be rare to be able to guess the exact form of the solution. Clearly we were lucky in this case.
In case the answer is supposed to be O(n^k), then the obvious guess is a polynomial of degree $k$ in $n$. In rare cases like this, that is all you need to do. The technique that you present if much more complicated using analysis and some transcendental functions. Also I does't match exactly my answer because all it cares about is $ O(n).$
answered Apr 8 at 22:00
SomosSomos
15k11337
$endgroup$
$begingroup$
Wow so the solution is based on the fact that you were able to make a guess that T(n) = a n + b ? Was there anything that pushed you to that, and is the solution in the post a similar technique?
$endgroup$
– Brownie
Apr 8 at 22:08
$begingroup$
Sorry if this something really obvious but how do you get that T(n) is O(n) from $T(n) = a n - c/(c-1) $
$endgroup$
– Brownie
Apr 9 at 1:25
1
$begingroup$
As the original solution states: "this function has complexity of $O(n)$ as it is a linear function." by definition of Big O notation.
$endgroup$
– Somos
Apr 9 at 1:41
add a comment |
Your Answer
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%2f3180165%2funderstanding-the-recurrence-relation-tn-ctn-c-1%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
$begingroup$
Assume a linear ansatz of $ T(n) := a n + b. $
The recursion equation we now have is
$$ T(n) = a n + b = c(T(n/c) + 1) = c( a n/c + b+1) = a n + b c + c. $$
Solve this equation to get $ b = -c/(c-1). $ Thus we have
$ T(n) = a n - c/(c-1) $ and $ T(n) = O(n) $ as we expected.
We need to find $ a $ using $ T(1)=1 $ with solution
$ a = (2c-1)/(c-1). $ Finally, $ T(n) = ((2c-1)n-c)/(c-1).$
The key to this solution is the ansatz which was a guess. It worked, but in general, it would be rare to be able to guess the exact form of the solution. Clearly we were lucky in this case.
In case the answer is supposed to be O(n^k), then the obvious guess is a polynomial of degree $k$ in $n$. In rare cases like this, that is all you need to do. The technique that you present if much more complicated using analysis and some transcendental functions. Also I does't match exactly my answer because all it cares about is $ O(n).$
answered Apr 8 at 22:00
SomosSomos
15k11337
$endgroup$
$begingroup$
Wow so the solution is based on the fact that you were able to make a guess that T(n) = a n + b ? Was there anything that pushed you to that, and is the solution in the post a similar technique?
$endgroup$
– Brownie
Apr 8 at 22:08
$begingroup$
Sorry if this something really obvious but how do you get that T(n) is O(n) from $T(n) = a n - c/(c-1) $
$endgroup$
– Brownie
Apr 9 at 1:25
1
$begingroup$
As the original solution states: "this function has complexity of $O(n)$ as it is a linear function." by definition of Big O notation.
$endgroup$
– Somos
Apr 9 at 1:41
add a comment |
$begingroup$
Assume a linear ansatz of $ T(n) := a n + b. $
The recursion equation we now have is
$$ T(n) = a n + b = c(T(n/c) + 1) = c( a n/c + b+1) = a n + b c + c. $$
Solve this equation to get $ b = -c/(c-1). $ Thus we have
$ T(n) = a n - c/(c-1) $ and $ T(n) = O(n) $ as we expected.
We need to find $ a $ using $ T(1)=1 $ with solution
$ a = (2c-1)/(c-1). $ Finally, $ T(n) = ((2c-1)n-c)/(c-1).$
The key to this solution is the ansatz which was a guess. It worked, but in general, it would be rare to be able to guess the exact form of the solution. Clearly we were lucky in this case.
In case the answer is supposed to be O(n^k), then the obvious guess is a polynomial of degree $k$ in $n$. In rare cases like this, that is all you need to do. The technique that you present if much more complicated using analysis and some transcendental functions. Also I does't match exactly my answer because all it cares about is $ O(n).$
answered Apr 8 at 22:00
SomosSomos
15k11337
$endgroup$
$begingroup$
Wow so the solution is based on the fact that you were able to make a guess that T(n) = a n + b ? Was there anything that pushed you to that, and is the solution in the post a similar technique?
$endgroup$
– Brownie
Apr 8 at 22:08
$begingroup$
Sorry if this something really obvious but how do you get that T(n) is O(n) from $T(n) = a n - c/(c-1) $
$endgroup$
– Brownie
Apr 9 at 1:25
1
$begingroup$
As the original solution states: "this function has complexity of $O(n)$ as it is a linear function." by definition of Big O notation.
$endgroup$
– Somos
Apr 9 at 1:41
add a comment |
$begingroup$
Assume a linear ansatz of $ T(n) := a n + b. $
The recursion equation we now have is
$$ T(n) = a n + b = c(T(n/c) + 1) = c( a n/c + b+1) = a n + b c + c. $$
Solve this equation to get $ b = -c/(c-1). $ Thus we have
$ T(n) = a n - c/(c-1) $ and $ T(n) = O(n) $ as we expected.
We need to find $ a $ using $ T(1)=1 $ with solution
$ a = (2c-1)/(c-1). $ Finally, $ T(n) = ((2c-1)n-c)/(c-1).$
The key to this solution is the ansatz which was a guess. It worked, but in general, it would be rare to be able to guess the exact form of the solution. Clearly we were lucky in this case.
In case the answer is supposed to be O(n^k), then the obvious guess is a polynomial of degree $k$ in $n$. In rare cases like this, that is all you need to do. The technique that you present if much more complicated using analysis and some transcendental functions. Also I does't match exactly my answer because all it cares about is $ O(n).$
answered Apr 8 at 22:00
SomosSomos
15k11337
$endgroup$
Assume a linear ansatz of $ T(n) := a n + b. $
The recursion equation we now have is
$$ T(n) = a n + b = c(T(n/c) + 1) = c( a n/c + b+1) = a n + b c + c. $$
Solve this equation to get $ b = -c/(c-1). $ Thus we have
$ T(n) = a n - c/(c-1) $ and $ T(n) = O(n) $ as we expected.
We need to find $ a $ using $ T(1)=1 $ with solution
$ a = (2c-1)/(c-1). $ Finally, $ T(n) = ((2c-1)n-c)/(c-1).$
The key to this solution is the ansatz which was a guess. It worked, but in general, it would be rare to be able to guess the exact form of the solution. Clearly we were lucky in this case.
In case the answer is supposed to be O(n^k), then the obvious guess is a polynomial of degree $k$ in $n$. In rare cases like this, that is all you need to do. The technique that you present if much more complicated using analysis and some transcendental functions. Also I does't match exactly my answer because all it cares about is $ O(n).$
answered Apr 8 at 22:00
SomosSomos
15k11337
edited Apr 8 at 22:27
answered Apr 8 at 22:00
SomosSomos
15k11337
answered Apr 8 at 22:00
SomosSomos
15k11337
answered Apr 8 at 22:00
SomosSomos
15k11337
15k11337
$begingroup$
Wow so the solution is based on the fact that you were able to make a guess that T(n) = a n + b ? Was there anything that pushed you to that, and is the solution in the post a similar technique?
$endgroup$
– Brownie
Apr 8 at 22:08
$begingroup$
Sorry if this something really obvious but how do you get that T(n) is O(n) from $T(n) = a n - c/(c-1) $
$endgroup$
– Brownie
Apr 9 at 1:25
1
$begingroup$
As the original solution states: "this function has complexity of $O(n)$ as it is a linear function." by definition of Big O notation.
$endgroup$
– Somos
Apr 9 at 1:41
add a comment |
$begingroup$
Wow so the solution is based on the fact that you were able to make a guess that T(n) = a n + b ? Was there anything that pushed you to that, and is the solution in the post a similar technique?
$endgroup$
– Brownie
Apr 8 at 22:08
$begingroup$
Sorry if this something really obvious but how do you get that T(n) is O(n) from $T(n) = a n - c/(c-1) $
$endgroup$
– Brownie
Apr 9 at 1:25
1
$begingroup$
As the original solution states: "this function has complexity of $O(n)$ as it is a linear function." by definition of Big O notation.
$endgroup$
– Somos
Apr 9 at 1:41
$begingroup$
Wow so the solution is based on the fact that you were able to make a guess that T(n) = a n + b ? Was there anything that pushed you to that, and is the solution in the post a similar technique?
$endgroup$
– Brownie
Apr 8 at 22:08
$begingroup$
Wow so the solution is based on the fact that you were able to make a guess that T(n) = a n + b ? Was there anything that pushed you to that, and is the solution in the post a similar technique?
$endgroup$
– Brownie
Apr 8 at 22:08
$begingroup$
Sorry if this something really obvious but how do you get that T(n) is O(n) from $T(n) = a n - c/(c-1) $
$endgroup$
– Brownie
Apr 9 at 1:25
$begingroup$
Sorry if this something really obvious but how do you get that T(n) is O(n) from $T(n) = a n - c/(c-1) $
$endgroup$
– Brownie
Apr 9 at 1:25
1
1
$begingroup$
As the original solution states: "this function has complexity of $O(n)$ as it is a linear function." by definition of Big O notation.
$endgroup$
– Somos
Apr 9 at 1:41
$begingroup$
As the original solution states: "this function has complexity of $O(n)$ as it is a linear function." by definition of Big O notation.
$endgroup$
– Somos
Apr 9 at 1:41
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%2f3180165%2funderstanding-the-recurrence-relation-tn-ctn-c-1%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
