Recurrence proof by induction
I'm having a hard time to understand how am i supposed to solve this question:
$T(n) = sqrt{n}T(sqrt{n})+n$. Prove by induction that $T(n) = Theta (n log{(log{(n)})})$.
These are all the data I got. where do i start from? what is the base case? i'm not really sure...
Thanks!
algorithms induction recursive-algorithms
edited Dec 7 at 15:45
tarit goswami
1,7031421
asked Dec 7 at 15:35
Sahar Malka
31
add a comment |
I'm having a hard time to understand how am i supposed to solve this question:
$T(n) = sqrt{n}T(sqrt{n})+n$. Prove by induction that $T(n) = Theta (n log{(log{(n)})})$.
These are all the data I got. where do i start from? what is the base case? i'm not really sure...
Thanks!
algorithms induction recursive-algorithms
edited Dec 7 at 15:45
tarit goswami
1,7031421
asked Dec 7 at 15:35
Sahar Malka
31
1
What happen at $T(1)$?
– user10354138
Dec 7 at 16:01
add a comment |
I'm having a hard time to understand how am i supposed to solve this question:
$T(n) = sqrt{n}T(sqrt{n})+n$. Prove by induction that $T(n) = Theta (n log{(log{(n)})})$.
These are all the data I got. where do i start from? what is the base case? i'm not really sure...
Thanks!
algorithms induction recursive-algorithms
edited Dec 7 at 15:45
tarit goswami
1,7031421
asked Dec 7 at 15:35
Sahar Malka
31
I'm having a hard time to understand how am i supposed to solve this question:
$T(n) = sqrt{n}T(sqrt{n})+n$. Prove by induction that $T(n) = Theta (n log{(log{(n)})})$.
These are all the data I got. where do i start from? what is the base case? i'm not really sure...
Thanks!
algorithms induction recursive-algorithms
algorithms induction recursive-algorithms
edited Dec 7 at 15:45
tarit goswami
1,7031421
asked Dec 7 at 15:35
Sahar Malka
31
edited Dec 7 at 15:45
tarit goswami
1,7031421
asked Dec 7 at 15:35
Sahar Malka
31
edited Dec 7 at 15:45
tarit goswami
1,7031421
edited Dec 7 at 15:45
tarit goswami
1,7031421
edited Dec 7 at 15:45
tarit goswami
1,7031421
1,7031421
asked Dec 7 at 15:35
Sahar Malka
31
asked Dec 7 at 15:35
Sahar Malka
31
asked Dec 7 at 15:35
Sahar Malka
31
31
1
What happen at $T(1)$?
– user10354138
Dec 7 at 16:01
add a comment |
1
What happen at $T(1)$?
– user10354138
Dec 7 at 16:01
1
1
What happen at $T(1)$?
– user10354138
Dec 7 at 16:01
What happen at $T(1)$?
– user10354138
Dec 7 at 16:01
add a comment |
1 Answer
1
active
oldest
votes
I assume $sqrt{n}$ refers to the integer square root, where you round down.
You prove it by strong induction. Assume that $T(n)le Cnlog log n$ for some all $n$ satisfying $n_0le n<m$, for a constant $C$ to be determined later. Then
$$
T(m)=sqrt{m}T(sqrt{m})+mle sqrt{m}cdot Csqrt{m}log log sqrt{m}+m =mcdot big(Clog log m+Clog tfrac12 +1big)
$$
We want this last expression to at most $Cloglog m$, completing the strong induction proof. Assuming this implies $Cgefrac1{log 2}$.
To figure out the base cases, look at what the induction hypothesis needs. For the above to work, you need the $sqrt{m}$ to be previously proven, so the set of base cases need to be a set $B$ such that repeated application of $sqrt{cdot}$ always sends an integer to $B$. It turns out that $B={2,3}$ works. Therefore, this induction proof works for any choice of $C$ such that $Cge frac1{log 2}$ and $T(2)le Ccdot 2log log 2$ and $T(3)le Ccdot 3log log 3$.
answered Dec 7 at 16:21
Mike Earnest
20.1k11950
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%2f3030020%2frecurrence-proof-by-induction%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
I assume $sqrt{n}$ refers to the integer square root, where you round down.
You prove it by strong induction. Assume that $T(n)le Cnlog log n$ for some all $n$ satisfying $n_0le n<m$, for a constant $C$ to be determined later. Then
$$
T(m)=sqrt{m}T(sqrt{m})+mle sqrt{m}cdot Csqrt{m}log log sqrt{m}+m =mcdot big(Clog log m+Clog tfrac12 +1big)
$$
We want this last expression to at most $Cloglog m$, completing the strong induction proof. Assuming this implies $Cgefrac1{log 2}$.
To figure out the base cases, look at what the induction hypothesis needs. For the above to work, you need the $sqrt{m}$ to be previously proven, so the set of base cases need to be a set $B$ such that repeated application of $sqrt{cdot}$ always sends an integer to $B$. It turns out that $B={2,3}$ works. Therefore, this induction proof works for any choice of $C$ such that $Cge frac1{log 2}$ and $T(2)le Ccdot 2log log 2$ and $T(3)le Ccdot 3log log 3$.
answered Dec 7 at 16:21
Mike Earnest
20.1k11950
add a comment |
I assume $sqrt{n}$ refers to the integer square root, where you round down.
You prove it by strong induction. Assume that $T(n)le Cnlog log n$ for some all $n$ satisfying $n_0le n<m$, for a constant $C$ to be determined later. Then
$$
T(m)=sqrt{m}T(sqrt{m})+mle sqrt{m}cdot Csqrt{m}log log sqrt{m}+m =mcdot big(Clog log m+Clog tfrac12 +1big)
$$
We want this last expression to at most $Cloglog m$, completing the strong induction proof. Assuming this implies $Cgefrac1{log 2}$.
To figure out the base cases, look at what the induction hypothesis needs. For the above to work, you need the $sqrt{m}$ to be previously proven, so the set of base cases need to be a set $B$ such that repeated application of $sqrt{cdot}$ always sends an integer to $B$. It turns out that $B={2,3}$ works. Therefore, this induction proof works for any choice of $C$ such that $Cge frac1{log 2}$ and $T(2)le Ccdot 2log log 2$ and $T(3)le Ccdot 3log log 3$.
answered Dec 7 at 16:21
Mike Earnest
20.1k11950
add a comment |
I assume $sqrt{n}$ refers to the integer square root, where you round down.
You prove it by strong induction. Assume that $T(n)le Cnlog log n$ for some all $n$ satisfying $n_0le n<m$, for a constant $C$ to be determined later. Then
$$
T(m)=sqrt{m}T(sqrt{m})+mle sqrt{m}cdot Csqrt{m}log log sqrt{m}+m =mcdot big(Clog log m+Clog tfrac12 +1big)
$$
We want this last expression to at most $Cloglog m$, completing the strong induction proof. Assuming this implies $Cgefrac1{log 2}$.
To figure out the base cases, look at what the induction hypothesis needs. For the above to work, you need the $sqrt{m}$ to be previously proven, so the set of base cases need to be a set $B$ such that repeated application of $sqrt{cdot}$ always sends an integer to $B$. It turns out that $B={2,3}$ works. Therefore, this induction proof works for any choice of $C$ such that $Cge frac1{log 2}$ and $T(2)le Ccdot 2log log 2$ and $T(3)le Ccdot 3log log 3$.
answered Dec 7 at 16:21
Mike Earnest
20.1k11950
I assume $sqrt{n}$ refers to the integer square root, where you round down.
You prove it by strong induction. Assume that $T(n)le Cnlog log n$ for some all $n$ satisfying $n_0le n<m$, for a constant $C$ to be determined later. Then
$$
T(m)=sqrt{m}T(sqrt{m})+mle sqrt{m}cdot Csqrt{m}log log sqrt{m}+m =mcdot big(Clog log m+Clog tfrac12 +1big)
$$
We want this last expression to at most $Cloglog m$, completing the strong induction proof. Assuming this implies $Cgefrac1{log 2}$.
To figure out the base cases, look at what the induction hypothesis needs. For the above to work, you need the $sqrt{m}$ to be previously proven, so the set of base cases need to be a set $B$ such that repeated application of $sqrt{cdot}$ always sends an integer to $B$. It turns out that $B={2,3}$ works. Therefore, this induction proof works for any choice of $C$ such that $Cge frac1{log 2}$ and $T(2)le Ccdot 2log log 2$ and $T(3)le Ccdot 3log log 3$.
answered Dec 7 at 16:21
Mike Earnest
20.1k11950
answered Dec 7 at 16:21
Mike Earnest
20.1k11950
answered Dec 7 at 16:21
Mike Earnest
20.1k11950
answered Dec 7 at 16:21
Mike Earnest
20.1k11950
20.1k11950
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3030020%2frecurrence-proof-by-induction%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
What happen at $T(1)$?
– user10354138
Dec 7 at 16:01