Mixing
Complexity of $T(n)=T(n - sqrtn)+n$
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
What is complexity of $T(n)=T(n - sqrtn)+n$
I tried to solve this with a few methods that I know but none of them helped me. So I decided to ask you for help.
recurrence-relations
asked Jul 25 at 18:10
Iman Roostaei
62
 |Â
show 2 more comments
up vote
0
down vote
favorite
What is complexity of $T(n)=T(n - sqrtn)+n$
I tried to solve this with a few methods that I know but none of them helped me. So I decided to ask you for help.
recurrence-relations
asked Jul 25 at 18:10
Iman Roostaei
62
3
Which few methods?
– Clement C.
Jul 25 at 18:13
@alxchen The induction is not quite correct, but the asymptotics are right. Under some mild assumptions on $T$ (monotone, etc.), we get $T(n) sim_ntoinfty frac23n^3/2$.
– Clement C.
Jul 25 at 18:19
Thanks. Could you prove it?
– Iman Roostaei
Jul 25 at 18:29
1
Yes, I can. (Proving that without the exact constant is not too hard.) But you, can you answer the question from my first comment? What have you tried, and how/why did it fail?
– Clement C.
Jul 25 at 18:29
I tried solving it by 1) changing the variable 2) guessing and using induction 3) transform relation to some kind which could be solved by the general formula.
– Iman Roostaei
Jul 25 at 18:39
 |Â
show 2 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
What is complexity of $T(n)=T(n - sqrtn)+n$
I tried to solve this with a few methods that I know but none of them helped me. So I decided to ask you for help.
recurrence-relations
asked Jul 25 at 18:10
Iman Roostaei
62
What is complexity of $T(n)=T(n - sqrtn)+n$
I tried to solve this with a few methods that I know but none of them helped me. So I decided to ask you for help.
recurrence-relations
asked Jul 25 at 18:10
Iman Roostaei
62
asked Jul 25 at 18:10
Iman Roostaei
62
asked Jul 25 at 18:10
Iman Roostaei
62
asked Jul 25 at 18:10
Iman Roostaei
62
62
3
Which few methods?
– Clement C.
Jul 25 at 18:13
@alxchen The induction is not quite correct, but the asymptotics are right. Under some mild assumptions on $T$ (monotone, etc.), we get $T(n) sim_ntoinfty frac23n^3/2$.
– Clement C.
Jul 25 at 18:19
Thanks. Could you prove it?
– Iman Roostaei
Jul 25 at 18:29
1
Yes, I can. (Proving that without the exact constant is not too hard.) But you, can you answer the question from my first comment? What have you tried, and how/why did it fail?
– Clement C.
Jul 25 at 18:29
I tried solving it by 1) changing the variable 2) guessing and using induction 3) transform relation to some kind which could be solved by the general formula.
– Iman Roostaei
Jul 25 at 18:39
 |Â
show 2 more comments
3
Which few methods?
– Clement C.
Jul 25 at 18:13
@alxchen The induction is not quite correct, but the asymptotics are right. Under some mild assumptions on $T$ (monotone, etc.), we get $T(n) sim_ntoinfty frac23n^3/2$.
– Clement C.
Jul 25 at 18:19
Thanks. Could you prove it?
– Iman Roostaei
Jul 25 at 18:29
1
Yes, I can. (Proving that without the exact constant is not too hard.) But you, can you answer the question from my first comment? What have you tried, and how/why did it fail?
– Clement C.
Jul 25 at 18:29
I tried solving it by 1) changing the variable 2) guessing and using induction 3) transform relation to some kind which could be solved by the general formula.
– Iman Roostaei
Jul 25 at 18:39
3
3
Which few methods?
– Clement C.
Jul 25 at 18:13
Which few methods?
– Clement C.
Jul 25 at 18:13
@alxchen The induction is not quite correct, but the asymptotics are right. Under some mild assumptions on $T$ (monotone, etc.), we get $T(n) sim_ntoinfty frac23n^3/2$.
– Clement C.
Jul 25 at 18:19
@alxchen The induction is not quite correct, but the asymptotics are right. Under some mild assumptions on $T$ (monotone, etc.), we get $T(n) sim_ntoinfty frac23n^3/2$.
– Clement C.
Jul 25 at 18:19
Thanks. Could you prove it?
– Iman Roostaei
Jul 25 at 18:29
Thanks. Could you prove it?
– Iman Roostaei
Jul 25 at 18:29
1
1
Yes, I can. (Proving that without the exact constant is not too hard.) But you, can you answer the question from my first comment? What have you tried, and how/why did it fail?
– Clement C.
Jul 25 at 18:29
Yes, I can. (Proving that without the exact constant is not too hard.) But you, can you answer the question from my first comment? What have you tried, and how/why did it fail?
– Clement C.
Jul 25 at 18:29
I tried solving it by 1) changing the variable 2) guessing and using induction 3) transform relation to some kind which could be solved by the general formula.
– Iman Roostaei
Jul 25 at 18:39
I tried solving it by 1) changing the variable 2) guessing and using induction 3) transform relation to some kind which could be solved by the general formula.
– Iman Roostaei
Jul 25 at 18:39
 |Â
show 2 more comments
1 Answer
1
active
oldest
votes
up vote
3
down vote
Assuming $T$ is monotone, defined on the reals, and usual assumptions for the recurrence relation to make sense (i.e., not having to deal with corner cases and floors/ceilings).
We will show that $T(n) = Theta(n^3/2)$.
Why? The reason to assume this is the right thing to prove is heuristic:
$$
T(n) = T(n-sqrtn)+ n simeq T(n-2sqrtn)+ 2n-sqrtn simeq T(n-ksqrtn)+ kn-(k-1)sqrtn
$$
and we get $T(1)$ for $ksimeqsqrtn$, which leads to $T(n) simeq ksqrtn simeq n^3/2$. Of course, there were a lof of approximations made at every step, so we may want to actually prove it.Upper bound. Suppose there exists $Cgeq 1$ such that $T(k) leq Ck^3/2$ for every $k<n$. (The base case is easy, we just need $C$ to be chosen greater than the first few terms of $T$). Then
$$
T(n) = n + T(n-sqrtn) leq n + C(n-sqrtn)^3/2
leq Cn + C(n-sqrtn)^3/2 leq C n^3/2
$$
using the fact that
$$
x^3/2 geq (x-sqrtx)^3/2 + x, qquad xgeq 1,.
$$
(To see why this is true, observe that, dividing both sides by $x^3/2$, this is equivalent to $1-1/sqrtx geq (1-1/sqrtx)^3/2$).Lower bound. Same thing, by induction. Suppose $T(k) geq ck^3/2$ (for some small $cin(0,1/2)$ chosen based on the first terms $T(1),dots$) for every $k<n$. Then
$$
T(n) = n + T(n-sqrtn) geq n + c(n-sqrtn)^3/2
geq n + c(n^3/2-2n) geq cn^3/2
$$
since $cleq 1/2$, and using that
$$
(x-sqrtx)^3/2 geq x^3/2 - 2x,qquad xgeq 1
$$
(shown e.g. via calculus).
answered Jul 25 at 19:30
Clement C.
47k33682
2
(+1) Kudos for the economy (and accuracy) of the arguments.
– Did
Jul 25 at 19:47
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Assuming $T$ is monotone, defined on the reals, and usual assumptions for the recurrence relation to make sense (i.e., not having to deal with corner cases and floors/ceilings).
We will show that $T(n) = Theta(n^3/2)$.
Why? The reason to assume this is the right thing to prove is heuristic:
$$
T(n) = T(n-sqrtn)+ n simeq T(n-2sqrtn)+ 2n-sqrtn simeq T(n-ksqrtn)+ kn-(k-1)sqrtn
$$
and we get $T(1)$ for $ksimeqsqrtn$, which leads to $T(n) simeq ksqrtn simeq n^3/2$. Of course, there were a lof of approximations made at every step, so we may want to actually prove it.Upper bound. Suppose there exists $Cgeq 1$ such that $T(k) leq Ck^3/2$ for every $k<n$. (The base case is easy, we just need $C$ to be chosen greater than the first few terms of $T$). Then
$$
T(n) = n + T(n-sqrtn) leq n + C(n-sqrtn)^3/2
leq Cn + C(n-sqrtn)^3/2 leq C n^3/2
$$
using the fact that
$$
x^3/2 geq (x-sqrtx)^3/2 + x, qquad xgeq 1,.
$$
(To see why this is true, observe that, dividing both sides by $x^3/2$, this is equivalent to $1-1/sqrtx geq (1-1/sqrtx)^3/2$).Lower bound. Same thing, by induction. Suppose $T(k) geq ck^3/2$ (for some small $cin(0,1/2)$ chosen based on the first terms $T(1),dots$) for every $k<n$. Then
$$
T(n) = n + T(n-sqrtn) geq n + c(n-sqrtn)^3/2
geq n + c(n^3/2-2n) geq cn^3/2
$$
since $cleq 1/2$, and using that
$$
(x-sqrtx)^3/2 geq x^3/2 - 2x,qquad xgeq 1
$$
(shown e.g. via calculus).
answered Jul 25 at 19:30
Clement C.
47k33682
2
(+1) Kudos for the economy (and accuracy) of the arguments.
– Did
Jul 25 at 19:47
add a comment |Â
up vote
3
down vote
Assuming $T$ is monotone, defined on the reals, and usual assumptions for the recurrence relation to make sense (i.e., not having to deal with corner cases and floors/ceilings).
We will show that $T(n) = Theta(n^3/2)$.
Why? The reason to assume this is the right thing to prove is heuristic:
$$
T(n) = T(n-sqrtn)+ n simeq T(n-2sqrtn)+ 2n-sqrtn simeq T(n-ksqrtn)+ kn-(k-1)sqrtn
$$
and we get $T(1)$ for $ksimeqsqrtn$, which leads to $T(n) simeq ksqrtn simeq n^3/2$. Of course, there were a lof of approximations made at every step, so we may want to actually prove it.Upper bound. Suppose there exists $Cgeq 1$ such that $T(k) leq Ck^3/2$ for every $k<n$. (The base case is easy, we just need $C$ to be chosen greater than the first few terms of $T$). Then
$$
T(n) = n + T(n-sqrtn) leq n + C(n-sqrtn)^3/2
leq Cn + C(n-sqrtn)^3/2 leq C n^3/2
$$
using the fact that
$$
x^3/2 geq (x-sqrtx)^3/2 + x, qquad xgeq 1,.
$$
(To see why this is true, observe that, dividing both sides by $x^3/2$, this is equivalent to $1-1/sqrtx geq (1-1/sqrtx)^3/2$).Lower bound. Same thing, by induction. Suppose $T(k) geq ck^3/2$ (for some small $cin(0,1/2)$ chosen based on the first terms $T(1),dots$) for every $k<n$. Then
$$
T(n) = n + T(n-sqrtn) geq n + c(n-sqrtn)^3/2
geq n + c(n^3/2-2n) geq cn^3/2
$$
since $cleq 1/2$, and using that
$$
(x-sqrtx)^3/2 geq x^3/2 - 2x,qquad xgeq 1
$$
(shown e.g. via calculus).
answered Jul 25 at 19:30
Clement C.
47k33682
2
(+1) Kudos for the economy (and accuracy) of the arguments.
– Did
Jul 25 at 19:47
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Assuming $T$ is monotone, defined on the reals, and usual assumptions for the recurrence relation to make sense (i.e., not having to deal with corner cases and floors/ceilings).
We will show that $T(n) = Theta(n^3/2)$.
Why? The reason to assume this is the right thing to prove is heuristic:
$$
T(n) = T(n-sqrtn)+ n simeq T(n-2sqrtn)+ 2n-sqrtn simeq T(n-ksqrtn)+ kn-(k-1)sqrtn
$$
and we get $T(1)$ for $ksimeqsqrtn$, which leads to $T(n) simeq ksqrtn simeq n^3/2$. Of course, there were a lof of approximations made at every step, so we may want to actually prove it.Upper bound. Suppose there exists $Cgeq 1$ such that $T(k) leq Ck^3/2$ for every $k<n$. (The base case is easy, we just need $C$ to be chosen greater than the first few terms of $T$). Then
$$
T(n) = n + T(n-sqrtn) leq n + C(n-sqrtn)^3/2
leq Cn + C(n-sqrtn)^3/2 leq C n^3/2
$$
using the fact that
$$
x^3/2 geq (x-sqrtx)^3/2 + x, qquad xgeq 1,.
$$
(To see why this is true, observe that, dividing both sides by $x^3/2$, this is equivalent to $1-1/sqrtx geq (1-1/sqrtx)^3/2$).Lower bound. Same thing, by induction. Suppose $T(k) geq ck^3/2$ (for some small $cin(0,1/2)$ chosen based on the first terms $T(1),dots$) for every $k<n$. Then
$$
T(n) = n + T(n-sqrtn) geq n + c(n-sqrtn)^3/2
geq n + c(n^3/2-2n) geq cn^3/2
$$
since $cleq 1/2$, and using that
$$
(x-sqrtx)^3/2 geq x^3/2 - 2x,qquad xgeq 1
$$
(shown e.g. via calculus).
answered Jul 25 at 19:30
Clement C.
47k33682
Assuming $T$ is monotone, defined on the reals, and usual assumptions for the recurrence relation to make sense (i.e., not having to deal with corner cases and floors/ceilings).
We will show that $T(n) = Theta(n^3/2)$.
Why? The reason to assume this is the right thing to prove is heuristic:
$$
T(n) = T(n-sqrtn)+ n simeq T(n-2sqrtn)+ 2n-sqrtn simeq T(n-ksqrtn)+ kn-(k-1)sqrtn
$$
and we get $T(1)$ for $ksimeqsqrtn$, which leads to $T(n) simeq ksqrtn simeq n^3/2$. Of course, there were a lof of approximations made at every step, so we may want to actually prove it.Upper bound. Suppose there exists $Cgeq 1$ such that $T(k) leq Ck^3/2$ for every $k<n$. (The base case is easy, we just need $C$ to be chosen greater than the first few terms of $T$). Then
$$
T(n) = n + T(n-sqrtn) leq n + C(n-sqrtn)^3/2
leq Cn + C(n-sqrtn)^3/2 leq C n^3/2
$$
using the fact that
$$
x^3/2 geq (x-sqrtx)^3/2 + x, qquad xgeq 1,.
$$
(To see why this is true, observe that, dividing both sides by $x^3/2$, this is equivalent to $1-1/sqrtx geq (1-1/sqrtx)^3/2$).Lower bound. Same thing, by induction. Suppose $T(k) geq ck^3/2$ (for some small $cin(0,1/2)$ chosen based on the first terms $T(1),dots$) for every $k<n$. Then
$$
T(n) = n + T(n-sqrtn) geq n + c(n-sqrtn)^3/2
geq n + c(n^3/2-2n) geq cn^3/2
$$
since $cleq 1/2$, and using that
$$
(x-sqrtx)^3/2 geq x^3/2 - 2x,qquad xgeq 1
$$
(shown e.g. via calculus).
answered Jul 25 at 19:30
Clement C.
47k33682
edited Jul 25 at 19:51
answered Jul 25 at 19:30
Clement C.
47k33682
answered Jul 25 at 19:30
Clement C.
47k33682
answered Jul 25 at 19:30
Clement C.
47k33682
47k33682
2
(+1) Kudos for the economy (and accuracy) of the arguments.
– Did
Jul 25 at 19:47
add a comment |Â
2
(+1) Kudos for the economy (and accuracy) of the arguments.
– Did
Jul 25 at 19:47
2
2
(+1) Kudos for the economy (and accuracy) of the arguments.
– Did
Jul 25 at 19:47
(+1) Kudos for the economy (and accuracy) of the arguments.
– Did
Jul 25 at 19:47
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%2fmath.stackexchange.com%2fquestions%2f2862681%2fcomplexity-of-tn-tn-sqrtnn%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
3
Which few methods?
– Clement C.
Jul 25 at 18:13
@alxchen The induction is not quite correct, but the asymptotics are right. Under some mild assumptions on $T$ (monotone, etc.), we get $T(n) sim_ntoinfty frac23n^3/2$.
– Clement C.
Jul 25 at 18:19
Thanks. Could you prove it?
– Iman Roostaei
Jul 25 at 18:29
1
Yes, I can. (Proving that without the exact constant is not too hard.) But you, can you answer the question from my first comment? What have you tried, and how/why did it fail?
– Clement C.
Jul 25 at 18:29
I tried solving it by 1) changing the variable 2) guessing and using induction 3) transform relation to some kind which could be solved by the general formula.
– Iman Roostaei
Jul 25 at 18:39