Complexity for a reccurence relation
up vote
0
down vote
favorite
If $ T(n) = sqrt{2n}T(sqrt{2n} )+ {n ^ 2} $ , what is complexity of T(n)?
Well, I let $ n = {2 ^ k} $ , $ y(k) = frac{T({2 ^ k} )}{4 ^ k} $ and I tried to resolve this recurrence by iterations methods, but I saw that it not works here. How I can find the complexity for this recurrence?
recurrence-relations
asked Nov 15 at 10:14
Daniel
166
add a comment |
up vote
0
down vote
favorite
If $ T(n) = sqrt{2n}T(sqrt{2n} )+ {n ^ 2} $ , what is complexity of T(n)?
Well, I let $ n = {2 ^ k} $ , $ y(k) = frac{T({2 ^ k} )}{4 ^ k} $ and I tried to resolve this recurrence by iterations methods, but I saw that it not works here. How I can find the complexity for this recurrence?
recurrence-relations
asked Nov 15 at 10:14
Daniel
166
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
If $ T(n) = sqrt{2n}T(sqrt{2n} )+ {n ^ 2} $ , what is complexity of T(n)?
Well, I let $ n = {2 ^ k} $ , $ y(k) = frac{T({2 ^ k} )}{4 ^ k} $ and I tried to resolve this recurrence by iterations methods, but I saw that it not works here. How I can find the complexity for this recurrence?
recurrence-relations
asked Nov 15 at 10:14
Daniel
166
If $ T(n) = sqrt{2n}T(sqrt{2n} )+ {n ^ 2} $ , what is complexity of T(n)?
Well, I let $ n = {2 ^ k} $ , $ y(k) = frac{T({2 ^ k} )}{4 ^ k} $ and I tried to resolve this recurrence by iterations methods, but I saw that it not works here. How I can find the complexity for this recurrence?
recurrence-relations
recurrence-relations
asked Nov 15 at 10:14
Daniel
166
asked Nov 15 at 10:14
Daniel
166
asked Nov 15 at 10:14
Daniel
166
asked Nov 15 at 10:14
Daniel
166
asked Nov 15 at 10:14
Daniel
166
166
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Try substituting $n$ by $2^{k+1}$ and consider $S(k)=frac{T(2^{k+1})}{2^{k+1}}$ which is $T(n)/n$ and this in turn is equal to $2frac{T(sqrt{2n})}{sqrt{2n}} + n$. By observing that $sqrt{2n}=2^{frac{k}{2}+1}$ you reduce your recurrence to a simpler one $S(k) = 2S(frac{k}{2})+2^{k+1}$. This you might find easier to solve.
answered Nov 15 at 11:32
Lacramioara
32126
Nice! It easier to solve now, thanks!
– Daniel
Nov 15 at 14:15
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Try substituting $n$ by $2^{k+1}$ and consider $S(k)=frac{T(2^{k+1})}{2^{k+1}}$ which is $T(n)/n$ and this in turn is equal to $2frac{T(sqrt{2n})}{sqrt{2n}} + n$. By observing that $sqrt{2n}=2^{frac{k}{2}+1}$ you reduce your recurrence to a simpler one $S(k) = 2S(frac{k}{2})+2^{k+1}$. This you might find easier to solve.
answered Nov 15 at 11:32
Lacramioara
32126
Nice! It easier to solve now, thanks!
– Daniel
Nov 15 at 14:15
add a comment |
up vote
1
down vote
accepted
Try substituting $n$ by $2^{k+1}$ and consider $S(k)=frac{T(2^{k+1})}{2^{k+1}}$ which is $T(n)/n$ and this in turn is equal to $2frac{T(sqrt{2n})}{sqrt{2n}} + n$. By observing that $sqrt{2n}=2^{frac{k}{2}+1}$ you reduce your recurrence to a simpler one $S(k) = 2S(frac{k}{2})+2^{k+1}$. This you might find easier to solve.
answered Nov 15 at 11:32
Lacramioara
32126
Nice! It easier to solve now, thanks!
– Daniel
Nov 15 at 14:15
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Try substituting $n$ by $2^{k+1}$ and consider $S(k)=frac{T(2^{k+1})}{2^{k+1}}$ which is $T(n)/n$ and this in turn is equal to $2frac{T(sqrt{2n})}{sqrt{2n}} + n$. By observing that $sqrt{2n}=2^{frac{k}{2}+1}$ you reduce your recurrence to a simpler one $S(k) = 2S(frac{k}{2})+2^{k+1}$. This you might find easier to solve.
answered Nov 15 at 11:32
Lacramioara
32126
Try substituting $n$ by $2^{k+1}$ and consider $S(k)=frac{T(2^{k+1})}{2^{k+1}}$ which is $T(n)/n$ and this in turn is equal to $2frac{T(sqrt{2n})}{sqrt{2n}} + n$. By observing that $sqrt{2n}=2^{frac{k}{2}+1}$ you reduce your recurrence to a simpler one $S(k) = 2S(frac{k}{2})+2^{k+1}$. This you might find easier to solve.
answered Nov 15 at 11:32
Lacramioara
32126
answered Nov 15 at 11:32
Lacramioara
32126
answered Nov 15 at 11:32
Lacramioara
32126
answered Nov 15 at 11:32
Lacramioara
32126
32126
Nice! It easier to solve now, thanks!
– Daniel
Nov 15 at 14:15
add a comment |
Nice! It easier to solve now, thanks!
– Daniel
Nov 15 at 14:15
Nice! It easier to solve now, thanks!
– Daniel
Nov 15 at 14:15
Nice! It easier to solve now, thanks!
– Daniel
Nov 15 at 14:15
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2999493%2fcomplexity-for-a-reccurence-relation%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
