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. The 2019 Stack Overflow Developer Survey Results Are InHow to solve recurrence relations with emphasis on algorithmic complexitySolve non-homogeneous recurrence relationHow does one solve recurrence relations involving subproblems of different sizes?Recurrence RelationUsing a recursion tree to obtain an algorithm classification with n^2 timeHow to solve recurrence $T(n) = T(n/3) + T(2n/3) +n$ using Master TheoremSolve the Recurrence Relation T(n)=sum of T(i)T(n-i)Using recursion trees to solve this recurrence relationUnderstanding the Master Theorem - Determining the levels of recursionHow do you solve a linear recurrence relation for $a_n$ given the solution
Ubuntu Server install with full GUI
What force causes entropy to increase?
Getting crown tickets for Statue of Liberty
"as much details as you can remember"
How do PCB vias affect signal quality?
What is preventing me from simply constructing a hash that's lower than the current target?
writing variables above the numbers in tikz picture
What is the meaning of Triage in Cybersec world?
How to charge AirPods to keep battery healthy?
Mathematics of imaging the black hole
How can I define good in a religion that claims no moral authority?
Did Scotland spend $250,000 for the slogan "Welcome to Scotland"?
RequirePermission not working
What is this sharp, curved notch on my knife for?
What does Linus Torvalds mean when he says that Git "never ever" tracks a file?
How to quickly solve partial fractions equation?
Is there a way to generate a uniformly distributed point on a sphere from a fixed amount of random real numbers?
Can a flute soloist sit?
Correct punctuation for showing a character's confusion
Kerning for subscripts of sigma?
The phrase "to the numbers born"?
Why can't devices on different VLANs, but on the same subnet, communicate?
How do you keep chess fun when your opponent constantly beats you?
Why isn't the circumferential light around the M87 black hole's event horizon symmetric?
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.
The 2019 Stack Overflow Developer Survey Results Are InHow to solve recurrence relations with emphasis on algorithmic complexitySolve non-homogeneous recurrence relationHow does one solve recurrence relations involving subproblems of different sizes?Recurrence RelationUsing a recursion tree to obtain an algorithm classification with n^2 timeHow to solve recurrence $T(n) = T(n/3) + T(2n/3) +n$ using Master TheoremSolve the Recurrence Relation T(n)=sum of T(i)T(n-i)Using recursion trees to solve this recurrence relationUnderstanding the Master Theorem - Determining the levels of recursionHow do you solve a linear recurrence relation for $a_n$ given the solution
$begingroup$
I'm a complete beginner at this, and was having trouble with this problem.
looking at $T(n) = c(T(n/c) + 1)$. I'm pretty sure its in the form of
f(n) = af(n/b) + Cnd
I think the master theorem can be used to get the answer, but I'm not sure how to get the values to compare a to $b^d$
Here is what I know
a is the number of subproblems
n/b is the subproblem size
Cnd is the time to be spend during each recursion level (C is a constant)
I'm not sure how to apply this, or if it's the right solution.
discrete-mathematics recurrence-relations computer-science
edited Apr 7 at 21:48
David G. Stork
12.1k41836
asked Apr 7 at 21:20
BrownieBrownie
3327
$endgroup$
add a comment |
$begingroup$
I'm a complete beginner at this, and was having trouble with this problem.
looking at $T(n) = c(T(n/c) + 1)$. I'm pretty sure its in the form of
f(n) = af(n/b) + Cnd
I think the master theorem can be used to get the answer, but I'm not sure how to get the values to compare a to $b^d$
Here is what I know
a is the number of subproblems
n/b is the subproblem size
Cnd is the time to be spend during each recursion level (C is a constant)
I'm not sure how to apply this, or if it's the right solution.
discrete-mathematics recurrence-relations computer-science
edited Apr 7 at 21:48
David G. Stork
12.1k41836
asked Apr 7 at 21:20
BrownieBrownie
3327
$endgroup$
$begingroup$
This looks like a great break down, but I really not very experienced in this. I'm having a lot of trouble following what your doing. You said to think of the inputs (n) in the form of $c^k$ , I see you do the replacing, but then I lose you when you put it equal to $c^2T(c^k-2)+c+1 ... = c^kT(1)+1+c+c^2+...+c^k-1$. Also how come you let T(1) = a?
$endgroup$
– Brownie
Apr 7 at 21:31
$begingroup$
One last thing, since it's in its general form how can i found the expression in Big-Oh notation? Orignally I was going to use the master theorem to compare a and $b^d$ but now I'm not sure
$endgroup$
– Brownie
Apr 7 at 21:34
$begingroup$
Once you have the general form, you look for the term that grows the fastest. That is your big O
$endgroup$
– Don Thousand
Apr 7 at 21:35
add a comment |
$begingroup$
I'm a complete beginner at this, and was having trouble with this problem.
looking at $T(n) = c(T(n/c) + 1)$. I'm pretty sure its in the form of
f(n) = af(n/b) + Cnd
I think the master theorem can be used to get the answer, but I'm not sure how to get the values to compare a to $b^d$
Here is what I know
a is the number of subproblems
n/b is the subproblem size
Cnd is the time to be spend during each recursion level (C is a constant)
I'm not sure how to apply this, or if it's the right solution.
discrete-mathematics recurrence-relations computer-science
edited Apr 7 at 21:48
David G. Stork
12.1k41836
asked Apr 7 at 21:20
BrownieBrownie
3327
$endgroup$
I'm a complete beginner at this, and was having trouble with this problem.
looking at $T(n) = c(T(n/c) + 1)$. I'm pretty sure its in the form of
f(n) = af(n/b) + Cnd
I think the master theorem can be used to get the answer, but I'm not sure how to get the values to compare a to $b^d$
Here is what I know
a is the number of subproblems
n/b is the subproblem size
Cnd is the time to be spend during each recursion level (C is a constant)
I'm not sure how to apply this, or if it's the right solution.
discrete-mathematics recurrence-relations computer-science
discrete-mathematics recurrence-relations computer-science
edited Apr 7 at 21:48
David G. Stork
12.1k41836
asked Apr 7 at 21:20
BrownieBrownie
3327
edited Apr 7 at 21:48
David G. Stork
12.1k41836
asked Apr 7 at 21:20
BrownieBrownie
3327
edited Apr 7 at 21:48
David G. Stork
12.1k41836
edited Apr 7 at 21:48
David G. Stork
12.1k41836
edited Apr 7 at 21:48
David G. Stork
12.1k41836
12.1k41836
asked Apr 7 at 21:20
BrownieBrownie
3327
asked Apr 7 at 21:20
BrownieBrownie
3327
asked Apr 7 at 21:20
BrownieBrownie
3327
3327
$begingroup$
This looks like a great break down, but I really not very experienced in this. I'm having a lot of trouble following what your doing. You said to think of the inputs (n) in the form of $c^k$ , I see you do the replacing, but then I lose you when you put it equal to $c^2T(c^k-2)+c+1 ... = c^kT(1)+1+c+c^2+...+c^k-1$. Also how come you let T(1) = a?
$endgroup$
– Brownie
Apr 7 at 21:31
$begingroup$
One last thing, since it's in its general form how can i found the expression in Big-Oh notation? Orignally I was going to use the master theorem to compare a and $b^d$ but now I'm not sure
$endgroup$
– Brownie
Apr 7 at 21:34
$begingroup$
Once you have the general form, you look for the term that grows the fastest. That is your big O
$endgroup$
– Don Thousand
Apr 7 at 21:35
add a comment |
$begingroup$
This looks like a great break down, but I really not very experienced in this. I'm having a lot of trouble following what your doing. You said to think of the inputs (n) in the form of $c^k$ , I see you do the replacing, but then I lose you when you put it equal to $c^2T(c^k-2)+c+1 ... = c^kT(1)+1+c+c^2+...+c^k-1$. Also how come you let T(1) = a?
$endgroup$
– Brownie
Apr 7 at 21:31
$begingroup$
One last thing, since it's in its general form how can i found the expression in Big-Oh notation? Orignally I was going to use the master theorem to compare a and $b^d$ but now I'm not sure
$endgroup$
– Brownie
Apr 7 at 21:34
$begingroup$
Once you have the general form, you look for the term that grows the fastest. That is your big O
$endgroup$
– Don Thousand
Apr 7 at 21:35
$begingroup$
This looks like a great break down, but I really not very experienced in this. I'm having a lot of trouble following what your doing. You said to think of the inputs (n) in the form of $c^k$ , I see you do the replacing, but then I lose you when you put it equal to $c^2T(c^k-2)+c+1 ... = c^kT(1)+1+c+c^2+...+c^k-1$. Also how come you let T(1) = a?
$endgroup$
– Brownie
Apr 7 at 21:31
$begingroup$
This looks like a great break down, but I really not very experienced in this. I'm having a lot of trouble following what your doing. You said to think of the inputs (n) in the form of $c^k$ , I see you do the replacing, but then I lose you when you put it equal to $c^2T(c^k-2)+c+1 ... = c^kT(1)+1+c+c^2+...+c^k-1$. Also how come you let T(1) = a?
$endgroup$
– Brownie
Apr 7 at 21:31
$begingroup$
One last thing, since it's in its general form how can i found the expression in Big-Oh notation? Orignally I was going to use the master theorem to compare a and $b^d$ but now I'm not sure
$endgroup$
– Brownie
Apr 7 at 21:34
$begingroup$
One last thing, since it's in its general form how can i found the expression in Big-Oh notation? Orignally I was going to use the master theorem to compare a and $b^d$ but now I'm not sure
$endgroup$
– Brownie
Apr 7 at 21:34
$begingroup$
Once you have the general form, you look for the term that grows the fastest. That is your big O
$endgroup$
– Don Thousand
Apr 7 at 21:35
$begingroup$
Once you have the general form, you look for the term that grows the fastest. That is your big O
$endgroup$
– Don Thousand
Apr 7 at 21:35
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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.
answered Apr 7 at 21:41
Don ThousandDon Thousand
4,574734
$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%2f3178801%2fsolve-the-recurrence-relation-tn-ctn-c-1-t1-1-by-finding-an-ex%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$
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.
answered Apr 7 at 21:41
Don ThousandDon Thousand
4,574734
$endgroup$
add a comment |
$begingroup$
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.
answered Apr 7 at 21:41
Don ThousandDon Thousand
4,574734
$endgroup$
add a comment |
$begingroup$
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.
answered Apr 7 at 21:41
Don ThousandDon Thousand
4,574734
$endgroup$
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.
answered Apr 7 at 21:41
Don ThousandDon Thousand
4,574734
answered Apr 7 at 21:41
Don ThousandDon Thousand
4,574734
answered Apr 7 at 21:41
Don ThousandDon Thousand
4,574734
answered Apr 7 at 21:41
Don ThousandDon Thousand
4,574734
4,574734
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%2f3178801%2fsolve-the-recurrence-relation-tn-ctn-c-1-t1-1-by-finding-an-ex%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$
This looks like a great break down, but I really not very experienced in this. I'm having a lot of trouble following what your doing. You said to think of the inputs (n) in the form of $c^k$ , I see you do the replacing, but then I lose you when you put it equal to $c^2T(c^k-2)+c+1 ... = c^kT(1)+1+c+c^2+...+c^k-1$. Also how come you let T(1) = a?
$endgroup$
– Brownie
Apr 7 at 21:31
$begingroup$
One last thing, since it's in its general form how can i found the expression in Big-Oh notation? Orignally I was going to use the master theorem to compare a and $b^d$ but now I'm not sure
$endgroup$
– Brownie
Apr 7 at 21:34
$begingroup$
Once you have the general form, you look for the term that grows the fastest. That is your big O
$endgroup$
– Don Thousand
Apr 7 at 21:35