Mixing
Removing arithmetic within recurrences
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
A similar question was asked here: Solving recurrences using substitution method, but I am still somewhat hazy as to how this process works.
Say, for $T(n) = T(lceil n/5 rceil + 36) + n log n$
Statement: we wish to prove that $T(n) le 5 n log n$ for $n ge 0$
Base case, $n = 0$ and $T(0) le 0$
$T(0) = 0$
$T(0) le 0 log 0$
Holds, since $0 log 0 = 0$
Inductive step, for $n > 0$
(Inductive Hypothesis is: $T(n) = 5 n log n$)
$T(n) = T(lceil n/5 rceil + 36) + n log n$
$le 5 , (lceil n/5 rceil + 36) log (lceil n/5 rceil + 36) + n log n$ by Ind. Hyp.
$le 5 , (n/5 + 36) log (n/5 + 36) + n log n$ by property of ceiling
$= (n + 180) log ((n + 180)/5) + n log n$ by algebra
This is the point where it gets hazy. According to the link, what I should do is say that for all $n ge 180$, then
$le (n + n) log ((n + n)/5) + n log n$
$= 2n log (2n/5) + n log n$
$= 2n , [log n + log (2/5)] + n log n$
$= 2n log n + 2n log (2/5) + n log n$
$= 3n log n + kn$ where $k = log (2/5) * 2$
$le 5n log n$
Does this complete the proof? Or am I in error? I still don't understand why I can just set $n ge 180$ and therefore get rid of the irritating arithmetic within the log.
asymptotics proof-techniques
edited Aug 26 at 7:41
Yuval Filmus
181k12171331
asked Aug 26 at 6:30
R. Rengold
1434
add a comment |Â
up vote
3
down vote
favorite
A similar question was asked here: Solving recurrences using substitution method, but I am still somewhat hazy as to how this process works.
Say, for $T(n) = T(lceil n/5 rceil + 36) + n log n$
Statement: we wish to prove that $T(n) le 5 n log n$ for $n ge 0$
Base case, $n = 0$ and $T(0) le 0$
$T(0) = 0$
$T(0) le 0 log 0$
Holds, since $0 log 0 = 0$
Inductive step, for $n > 0$
(Inductive Hypothesis is: $T(n) = 5 n log n$)
$T(n) = T(lceil n/5 rceil + 36) + n log n$
$le 5 , (lceil n/5 rceil + 36) log (lceil n/5 rceil + 36) + n log n$ by Ind. Hyp.
$le 5 , (n/5 + 36) log (n/5 + 36) + n log n$ by property of ceiling
$= (n + 180) log ((n + 180)/5) + n log n$ by algebra
This is the point where it gets hazy. According to the link, what I should do is say that for all $n ge 180$, then
$le (n + n) log ((n + n)/5) + n log n$
$= 2n log (2n/5) + n log n$
$= 2n , [log n + log (2/5)] + n log n$
$= 2n log n + 2n log (2/5) + n log n$
$= 3n log n + kn$ where $k = log (2/5) * 2$
$le 5n log n$
Does this complete the proof? Or am I in error? I still don't understand why I can just set $n ge 180$ and therefore get rid of the irritating arithmetic within the log.
asymptotics proof-techniques
edited Aug 26 at 7:41
Yuval Filmus
181k12171331
asked Aug 26 at 6:30
R. Rengold
1434
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
A similar question was asked here: Solving recurrences using substitution method, but I am still somewhat hazy as to how this process works.
Say, for $T(n) = T(lceil n/5 rceil + 36) + n log n$
Statement: we wish to prove that $T(n) le 5 n log n$ for $n ge 0$
Base case, $n = 0$ and $T(0) le 0$
$T(0) = 0$
$T(0) le 0 log 0$
Holds, since $0 log 0 = 0$
Inductive step, for $n > 0$
(Inductive Hypothesis is: $T(n) = 5 n log n$)
$T(n) = T(lceil n/5 rceil + 36) + n log n$
$le 5 , (lceil n/5 rceil + 36) log (lceil n/5 rceil + 36) + n log n$ by Ind. Hyp.
$le 5 , (n/5 + 36) log (n/5 + 36) + n log n$ by property of ceiling
$= (n + 180) log ((n + 180)/5) + n log n$ by algebra
This is the point where it gets hazy. According to the link, what I should do is say that for all $n ge 180$, then
$le (n + n) log ((n + n)/5) + n log n$
$= 2n log (2n/5) + n log n$
$= 2n , [log n + log (2/5)] + n log n$
$= 2n log n + 2n log (2/5) + n log n$
$= 3n log n + kn$ where $k = log (2/5) * 2$
$le 5n log n$
Does this complete the proof? Or am I in error? I still don't understand why I can just set $n ge 180$ and therefore get rid of the irritating arithmetic within the log.
asymptotics proof-techniques
edited Aug 26 at 7:41
Yuval Filmus
181k12171331
asked Aug 26 at 6:30
R. Rengold
1434
A similar question was asked here: Solving recurrences using substitution method, but I am still somewhat hazy as to how this process works.
Say, for $T(n) = T(lceil n/5 rceil + 36) + n log n$
Statement: we wish to prove that $T(n) le 5 n log n$ for $n ge 0$
Base case, $n = 0$ and $T(0) le 0$
$T(0) = 0$
$T(0) le 0 log 0$
Holds, since $0 log 0 = 0$
Inductive step, for $n > 0$
(Inductive Hypothesis is: $T(n) = 5 n log n$)
$T(n) = T(lceil n/5 rceil + 36) + n log n$
$le 5 , (lceil n/5 rceil + 36) log (lceil n/5 rceil + 36) + n log n$ by Ind. Hyp.
$le 5 , (n/5 + 36) log (n/5 + 36) + n log n$ by property of ceiling
$= (n + 180) log ((n + 180)/5) + n log n$ by algebra
This is the point where it gets hazy. According to the link, what I should do is say that for all $n ge 180$, then
$le (n + n) log ((n + n)/5) + n log n$
$= 2n log (2n/5) + n log n$
$= 2n , [log n + log (2/5)] + n log n$
$= 2n log n + 2n log (2/5) + n log n$
$= 3n log n + kn$ where $k = log (2/5) * 2$
$le 5n log n$
Does this complete the proof? Or am I in error? I still don't understand why I can just set $n ge 180$ and therefore get rid of the irritating arithmetic within the log.
asymptotics proof-techniques
edited Aug 26 at 7:41
Yuval Filmus
181k12171331
asked Aug 26 at 6:30
R. Rengold
1434
edited Aug 26 at 7:41
Yuval Filmus
181k12171331
edited Aug 26 at 7:41
Yuval Filmus
181k12171331
edited Aug 26 at 7:41
Yuval Filmus
181k12171331
181k12171331
asked Aug 26 at 6:30
R. Rengold
1434
asked Aug 26 at 6:30
R. Rengold
1434
asked Aug 26 at 6:30
R. Rengold
1434
1434
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
The link doesn't say what you say it does. I don't see the number 180 appearing anywhere on that link. And that link doesn't say the purpose is to prove $T(n) le 5 n log n$ for all $n ge 0$; it says to prove that $T(n) = O(n log n)$. Check the definition of big-O notation; it doesn't require proving $T(n) le c n log n$ for all $n ge 0$; it suffices to prove it for all $n ge 180$ (or for all $n ge n_0$ for any other constant $n_0$ of your choice).
answered Aug 26 at 6:40
D.W.♦
95.5k11110258
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
The link doesn't say what you say it does. I don't see the number 180 appearing anywhere on that link. And that link doesn't say the purpose is to prove $T(n) le 5 n log n$ for all $n ge 0$; it says to prove that $T(n) = O(n log n)$. Check the definition of big-O notation; it doesn't require proving $T(n) le c n log n$ for all $n ge 0$; it suffices to prove it for all $n ge 180$ (or for all $n ge n_0$ for any other constant $n_0$ of your choice).
answered Aug 26 at 6:40
D.W.♦
95.5k11110258
add a comment |Â
up vote
2
down vote
The link doesn't say what you say it does. I don't see the number 180 appearing anywhere on that link. And that link doesn't say the purpose is to prove $T(n) le 5 n log n$ for all $n ge 0$; it says to prove that $T(n) = O(n log n)$. Check the definition of big-O notation; it doesn't require proving $T(n) le c n log n$ for all $n ge 0$; it suffices to prove it for all $n ge 180$ (or for all $n ge n_0$ for any other constant $n_0$ of your choice).
answered Aug 26 at 6:40
D.W.♦
95.5k11110258
add a comment |Â
up vote
2
down vote
up vote
2
down vote
The link doesn't say what you say it does. I don't see the number 180 appearing anywhere on that link. And that link doesn't say the purpose is to prove $T(n) le 5 n log n$ for all $n ge 0$; it says to prove that $T(n) = O(n log n)$. Check the definition of big-O notation; it doesn't require proving $T(n) le c n log n$ for all $n ge 0$; it suffices to prove it for all $n ge 180$ (or for all $n ge n_0$ for any other constant $n_0$ of your choice).
answered Aug 26 at 6:40
D.W.♦
95.5k11110258
The link doesn't say what you say it does. I don't see the number 180 appearing anywhere on that link. And that link doesn't say the purpose is to prove $T(n) le 5 n log n$ for all $n ge 0$; it says to prove that $T(n) = O(n log n)$. Check the definition of big-O notation; it doesn't require proving $T(n) le c n log n$ for all $n ge 0$; it suffices to prove it for all $n ge 180$ (or for all $n ge n_0$ for any other constant $n_0$ of your choice).
answered Aug 26 at 6:40
D.W.♦
95.5k11110258
answered Aug 26 at 6:40
D.W.♦
95.5k11110258
answered Aug 26 at 6:40
D.W.♦
95.5k11110258
answered Aug 26 at 6:40
D.W.♦
95.5k11110258
95.5k11110258
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f96630%2fremoving-arithmetic-within-recurrences%23new-answer', 'question_page');
);
Post as a guest
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
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
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