Expand recursive equation to convert it into a normal formula
$begingroup$
The Problem:
I am faced with the following recursive equation:
$$V(n) =begin{cases}
2V(n/2)+n& text{for n > 1}\
0 &text{for n = 1}
end{cases}$$
I am trying to expand the function entirely and find a formula that is not recursive and is only dependent on n.
While I have proven by induction, that n log n works for that purpose, the expansion of the formula gives me a bit of trouble, since it doesn't seem even remotely related to n log n.
Question: How do I expand the recursive function above in a way, that clearly results in the formula n log n?
Here is what I have so far:
begin{eqnarray*}
V(n) &=& 2*V(n-1)+n\
&=& 2*(2*V(n-2)+(n-1))+n\
&=& 2*(2*(2*V(n-3)+(n-2))+(n-1))+n \
&vdots \
&=& nhspace{1mm} loghspace{1mm} n
end{eqnarray*}
I appreciate any help given!
recursion recursive-algorithms
asked Apr 14 '18 at 5:48
LuckyLucky
1107
$endgroup$
add a comment |
$begingroup$
The Problem:
I am faced with the following recursive equation:
$$V(n) =begin{cases}
2V(n/2)+n& text{for n > 1}\
0 &text{for n = 1}
end{cases}$$
I am trying to expand the function entirely and find a formula that is not recursive and is only dependent on n.
While I have proven by induction, that n log n works for that purpose, the expansion of the formula gives me a bit of trouble, since it doesn't seem even remotely related to n log n.
Question: How do I expand the recursive function above in a way, that clearly results in the formula n log n?
Here is what I have so far:
begin{eqnarray*}
V(n) &=& 2*V(n-1)+n\
&=& 2*(2*V(n-2)+(n-1))+n\
&=& 2*(2*(2*V(n-3)+(n-2))+(n-1))+n \
&vdots \
&=& nhspace{1mm} loghspace{1mm} n
end{eqnarray*}
I appreciate any help given!
recursion recursive-algorithms
asked Apr 14 '18 at 5:48
LuckyLucky
1107
$endgroup$
1
$begingroup$
Why do you have $V(n/2)$ in the problem but $V(n-1)$ in the expansion?
$endgroup$
– DanielV
Apr 14 '18 at 11:16
add a comment |
$begingroup$
The Problem:
I am faced with the following recursive equation:
$$V(n) =begin{cases}
2V(n/2)+n& text{for n > 1}\
0 &text{for n = 1}
end{cases}$$
I am trying to expand the function entirely and find a formula that is not recursive and is only dependent on n.
While I have proven by induction, that n log n works for that purpose, the expansion of the formula gives me a bit of trouble, since it doesn't seem even remotely related to n log n.
Question: How do I expand the recursive function above in a way, that clearly results in the formula n log n?
Here is what I have so far:
begin{eqnarray*}
V(n) &=& 2*V(n-1)+n\
&=& 2*(2*V(n-2)+(n-1))+n\
&=& 2*(2*(2*V(n-3)+(n-2))+(n-1))+n \
&vdots \
&=& nhspace{1mm} loghspace{1mm} n
end{eqnarray*}
I appreciate any help given!
recursion recursive-algorithms
asked Apr 14 '18 at 5:48
LuckyLucky
1107
$endgroup$
The Problem:
I am faced with the following recursive equation:
$$V(n) =begin{cases}
2V(n/2)+n& text{for n > 1}\
0 &text{for n = 1}
end{cases}$$
I am trying to expand the function entirely and find a formula that is not recursive and is only dependent on n.
While I have proven by induction, that n log n works for that purpose, the expansion of the formula gives me a bit of trouble, since it doesn't seem even remotely related to n log n.
Question: How do I expand the recursive function above in a way, that clearly results in the formula n log n?
Here is what I have so far:
begin{eqnarray*}
V(n) &=& 2*V(n-1)+n\
&=& 2*(2*V(n-2)+(n-1))+n\
&=& 2*(2*(2*V(n-3)+(n-2))+(n-1))+n \
&vdots \
&=& nhspace{1mm} loghspace{1mm} n
end{eqnarray*}
I appreciate any help given!
recursion recursive-algorithms
recursion recursive-algorithms
asked Apr 14 '18 at 5:48
LuckyLucky
1107
asked Apr 14 '18 at 5:48
LuckyLucky
1107
asked Apr 14 '18 at 5:48
LuckyLucky
1107
asked Apr 14 '18 at 5:48
LuckyLucky
1107
asked Apr 14 '18 at 5:48
LuckyLucky
1107
1107
1
$begingroup$
Why do you have $V(n/2)$ in the problem but $V(n-1)$ in the expansion?
$endgroup$
– DanielV
Apr 14 '18 at 11:16
add a comment |
1
$begingroup$
Why do you have $V(n/2)$ in the problem but $V(n-1)$ in the expansion?
$endgroup$
– DanielV
Apr 14 '18 at 11:16
1
1
$begingroup$
Why do you have $V(n/2)$ in the problem but $V(n-1)$ in the expansion?
$endgroup$
– DanielV
Apr 14 '18 at 11:16
$begingroup$
Why do you have $V(n/2)$ in the problem but $V(n-1)$ in the expansion?
$endgroup$
– DanielV
Apr 14 '18 at 11:16
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I think this belongs to Computer science, not to maths.
Have you heard of the Master-theorem? Try that, and you will see that the complexity is $O(nlog n)$.
Intuitively speaking, every time you have to divide your problem by 2 and add n steps (e.g. Quicksort, where you have to compare the pivot element with every other element). How many times do you have to divide? $log n$, because you split the problem in 2. So you have $log n$ steps, and on each step you have $O(n)$ steps, which makes time complexity of $O(n log n)$. If you are not familiar with the Big-O notation, see this article.
answered Jan 13 at 14:28
DreikäsehochDreikäsehoch
2797
$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%2f2736355%2fexpand-recursive-equation-to-convert-it-into-a-normal-formula%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$
I think this belongs to Computer science, not to maths.
Have you heard of the Master-theorem? Try that, and you will see that the complexity is $O(nlog n)$.
Intuitively speaking, every time you have to divide your problem by 2 and add n steps (e.g. Quicksort, where you have to compare the pivot element with every other element). How many times do you have to divide? $log n$, because you split the problem in 2. So you have $log n$ steps, and on each step you have $O(n)$ steps, which makes time complexity of $O(n log n)$. If you are not familiar with the Big-O notation, see this article.
answered Jan 13 at 14:28
DreikäsehochDreikäsehoch
2797
$endgroup$
add a comment |
$begingroup$
I think this belongs to Computer science, not to maths.
Have you heard of the Master-theorem? Try that, and you will see that the complexity is $O(nlog n)$.
Intuitively speaking, every time you have to divide your problem by 2 and add n steps (e.g. Quicksort, where you have to compare the pivot element with every other element). How many times do you have to divide? $log n$, because you split the problem in 2. So you have $log n$ steps, and on each step you have $O(n)$ steps, which makes time complexity of $O(n log n)$. If you are not familiar with the Big-O notation, see this article.
answered Jan 13 at 14:28
DreikäsehochDreikäsehoch
2797
$endgroup$
add a comment |
$begingroup$
I think this belongs to Computer science, not to maths.
Have you heard of the Master-theorem? Try that, and you will see that the complexity is $O(nlog n)$.
Intuitively speaking, every time you have to divide your problem by 2 and add n steps (e.g. Quicksort, where you have to compare the pivot element with every other element). How many times do you have to divide? $log n$, because you split the problem in 2. So you have $log n$ steps, and on each step you have $O(n)$ steps, which makes time complexity of $O(n log n)$. If you are not familiar with the Big-O notation, see this article.
answered Jan 13 at 14:28
DreikäsehochDreikäsehoch
2797
$endgroup$
I think this belongs to Computer science, not to maths.
Have you heard of the Master-theorem? Try that, and you will see that the complexity is $O(nlog n)$.
Intuitively speaking, every time you have to divide your problem by 2 and add n steps (e.g. Quicksort, where you have to compare the pivot element with every other element). How many times do you have to divide? $log n$, because you split the problem in 2. So you have $log n$ steps, and on each step you have $O(n)$ steps, which makes time complexity of $O(n log n)$. If you are not familiar with the Big-O notation, see this article.
answered Jan 13 at 14:28
DreikäsehochDreikäsehoch
2797
answered Jan 13 at 14:28
DreikäsehochDreikäsehoch
2797
answered Jan 13 at 14:28
DreikäsehochDreikäsehoch
2797
answered Jan 13 at 14:28
DreikäsehochDreikäsehoch
2797
2797
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%2f2736355%2fexpand-recursive-equation-to-convert-it-into-a-normal-formula%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$
Why do you have $V(n/2)$ in the problem but $V(n-1)$ in the expansion?
$endgroup$
– DanielV
Apr 14 '18 at 11:16