Fdtxjr

What is the significance behind "40 days" that often appears in the Bible?

Can I use USB data pins as power source

Professor being mistaken for a grad student

Fastest way to pop N items from a large dict

How to explain that I do not want to visit a country due to personal safety concern?

Aluminum electrolytic or ceramic capacitors for linear regulator input and output?

Why do passenger jet manufacturers design their planes with stall prevention systems?

World War I as a war of liberals against authoritarians?

Are Roman Catholic priests ever addressed as pastor

Equivalents to the present tense

Violin - Can double stops be played when the strings are not next to each other?

"of which" is correct here?

As a new Ubuntu desktop 18.04 LTS user, do I need to use ufw for a firewall or is iptables sufficient?

Is a party consisting of only a bard, a cleric, and a warlock functional long-term?

Bacteria contamination inside a thermos bottle

Bach's Toccata and Fugue in D minor breaks the "no parallel octaves" rule?

How could a scammer know the apps on my phone / iTunes account?

Is it good practice to use Linear Least-Squares with SMA?

Happy pi day, everyone!

Why does overlay work only on the first tcolorbox?

Is "upgrade" the right word to use in this context?

Do the common programs (for example: "ls", "cat") in Linux and BSD come from the same source code?

Shortcut for setting origin to vertex

What did “the good wine” (τὸν καλὸν οἶνον) mean in John 2:10?

Leaving recurrence summation in terms of $k$, $sum_i=0^k-1frac3^isqrtfrac n3^ilogfrac n3^i$

Finding the asymptotic behavior of the recurrence $T(n)=4T(fracn2)+n^2$ by using substitution methodHow to solve this recurrence $T(n)=2T(n/2)+n/log n$Find recurrence relation of $T(n)=2Tleft(leftlfloorsqrtnrightrfloorright)+log(n)$Algorithms - Solving the recurrence $T(n) = sqrtn T left(sqrt n right) + n$Solving the recurrence $T(n) = sqrt n T(sqrtn) + sqrtn$Solving the recurrence $3T(fracn4) + n cdot log n$ by the Recurrence Tree methodSolve recurrence $T(n) = T(frac34n) + sqrt n$Solve the Recurrence : $T(n)=3T(n/3) +fracnlog(n)$.Solving the recurrence $T(n) = 3Tleft(fracn3right) + nlog_2 n$Solving a recurrence relation: can't figure out how to convert from summation

1

$begingroup$

I have an exercise where I need to use the substitution method to solve the following recurrence and determine their corresponding complexity.
$$t(n)=3t(n/3) + fracsqrt nlog n$$
After some iterations, I got the following pattern.
$$t(n)=tleft(fracn3^kright)+sum_i=0^k-1frac3^isqrtn/3^ilog n/3^i$$

Honestly I do not know what kind of approach I could use to solve the summation, and leave everything in terms of $k$.

summation recurrence-relations recursive-algorithms

share|cite|improve this question

edited 2 days ago

Quantum A

asked Mar 1 at 6:29

Quantum AQuantum A

184

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
  $endgroup$
  – Shaun
  Mar 1 at 6:39
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @Shaun Hope is better now, thank you for the guidance!
  $endgroup$
  – Quantum A
  Mar 1 at 6:54
  

  
  
  
  

add a comment | 

1

$begingroup$

I have an exercise where I need to use the substitution method to solve the following recurrence and determine their corresponding complexity.
$$t(n)=3t(n/3) + fracsqrt nlog n$$
After some iterations, I got the following pattern.
$$t(n)=tleft(fracn3^kright)+sum_i=0^k-1frac3^isqrtn/3^ilog n/3^i$$

Honestly I do not know what kind of approach I could use to solve the summation, and leave everything in terms of $k$.

summation recurrence-relations recursive-algorithms

share|cite|improve this question

edited 2 days ago

Quantum A

asked Mar 1 at 6:29

Quantum AQuantum A

184

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
  $endgroup$
  – Shaun
  Mar 1 at 6:39
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @Shaun Hope is better now, thank you for the guidance!
  $endgroup$
  – Quantum A
  Mar 1 at 6:54
  

  
  
  
  

add a comment | 

$begingroup$

I have an exercise where I need to use the substitution method to solve the following recurrence and determine their corresponding complexity.
$$t(n)=3t(n/3) + fracsqrt nlog n$$
After some iterations, I got the following pattern.
$$t(n)=tleft(fracn3^kright)+sum_i=0^k-1frac3^isqrtn/3^ilog n/3^i$$

Honestly I do not know what kind of approach I could use to solve the summation, and leave everything in terms of $k$.

summation recurrence-relations recursive-algorithms

share|cite|improve this question

edited 2 days ago

Quantum A

asked Mar 1 at 6:29

Quantum AQuantum A

184

$endgroup$

share|cite|improve this question

edited 2 days ago

Quantum A

asked Mar 1 at 6:29

Quantum AQuantum A

184

share|cite|improve this question

edited 2 days ago

Quantum A

asked Mar 1 at 6:29

Quantum AQuantum A

184

asked Mar 1 at 6:29

Quantum AQuantum A

184

asked Mar 1 at 6:29

Quantum AQuantum A

184

2 Answers
2

active

oldest

votes

1

$begingroup$

Hint 1. As regards the asymptotic analysis (complexity?), you may use the Master Theorem. Then $c_crit=log_2(3)approx 1.58$ and $f(n)=fracn^1/2log(n)leq n^1/2$. What about $T(n)$?

Hint 2. Note that
$$t(2^n)=3^nt(1)+sum_k=0^n-1frac3^ksqrt2^n-klog (2^n-k)
=3^nt(1)+3^nsum_k=1^nfrac(sqrt2/3)^kklog (2)sim Ccdot 3^n$$
because the series $sum_k=1^nfrac(sqrt2/3)^kklog (2)$ is convergent (note that $sqrt2/3<1$).

share|cite|improve this answer

edited Mar 2 at 14:33

answered Mar 1 at 6:56

Robert ZRobert Z

101k1069142

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Hi Robert, Thank you so much for your advice, unfortunately I cannot use the Master Theorem this time, the instructions indicate that I should use substitution method for this complexity analysis, that is why is a big challenge.
  $endgroup$
  – Quantum A
  Mar 1 at 7:07
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @QuantumA Please read the new hint.
  $endgroup$
  – Robert Z
  Mar 1 at 16:02
  

  
  
  
  

add a comment | 

1

$begingroup$

$$
t(2^log_2 n) = 3 tleft(2^log_2left(frac u2right)right)+fracsqrt nln n
$$

now calling $T(u) = t(2^u)$ with $u = log_2 n$ we follow with

$$
T(u) = 3T(u-1) + frac2^frac u2uln 2
$$

This is a linear recurrence with solution $T(u) = T_h(u) + T_p(u)$

$$
begincases
T_h(u) = 3T_h(u-1) \
T_p(u) = 3T_p(u-1) + frac2^frac u2uln 2
endcases
$$

For the homogeneous we have

$$
T_h(u) = C_0 3^u
$$

and now making $T_p(u) = C_0(u) 3^u$ and substituting we have

$$
C_0(u)-C_0(u-1) = 3^-ufrac2^frac u2uln 2 = frac1lambdafracalpha^uu
$$

with $alpha = fracsqrt 23 < 1$ and $lambda = ln 2$

so we have

$$
C_0(u) = frac1lambdasum_k=1^ufracalpha^kk
$$

and then

$$
T(u) = left(C_0+frac1lambdasum_k=1^ufracalpha^kkright)3^u
$$

hence

$$
t(n) = left(C_0 + frac1ln 2sum_k=1^log_2 nfracalpha^kkright)3^log_2 n
$$

share|cite|improve this answer

answered Mar 12 at 8:27

CesareoCesareo

9,3963517

$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
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3131115%2fleaving-recurrence-summation-in-terms-of-k-sum-i-0k-1-frac3i-sqrt-f%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

Hint 1. As regards the asymptotic analysis (complexity?), you may use the Master Theorem. Then $c_crit=log_2(3)approx 1.58$ and $f(n)=fracn^1/2log(n)leq n^1/2$. What about $T(n)$?

Hint 2. Note that
$$t(2^n)=3^nt(1)+sum_k=0^n-1frac3^ksqrt2^n-klog (2^n-k)
=3^nt(1)+3^nsum_k=1^nfrac(sqrt2/3)^kklog (2)sim Ccdot 3^n$$
because the series $sum_k=1^nfrac(sqrt2/3)^kklog (2)$ is convergent (note that $sqrt2/3<1$).

share|cite|improve this answer

edited Mar 2 at 14:33

answered Mar 1 at 6:56

Robert ZRobert Z

101k1069142

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Hi Robert, Thank you so much for your advice, unfortunately I cannot use the Master Theorem this time, the instructions indicate that I should use substitution method for this complexity analysis, that is why is a big challenge.
  $endgroup$
  – Quantum A
  Mar 1 at 7:07
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @QuantumA Please read the new hint.
  $endgroup$
  – Robert Z
  Mar 1 at 16:02
  

  
  
  
  

add a comment | 

1

$begingroup$

Hint 1. As regards the asymptotic analysis (complexity?), you may use the Master Theorem. Then $c_crit=log_2(3)approx 1.58$ and $f(n)=fracn^1/2log(n)leq n^1/2$. What about $T(n)$?

Hint 2. Note that
$$t(2^n)=3^nt(1)+sum_k=0^n-1frac3^ksqrt2^n-klog (2^n-k)
=3^nt(1)+3^nsum_k=1^nfrac(sqrt2/3)^kklog (2)sim Ccdot 3^n$$
because the series $sum_k=1^nfrac(sqrt2/3)^kklog (2)$ is convergent (note that $sqrt2/3<1$).

share|cite|improve this answer

edited Mar 2 at 14:33

answered Mar 1 at 6:56

Robert ZRobert Z

101k1069142

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Hi Robert, Thank you so much for your advice, unfortunately I cannot use the Master Theorem this time, the instructions indicate that I should use substitution method for this complexity analysis, that is why is a big challenge.
  $endgroup$
  – Quantum A
  Mar 1 at 7:07
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @QuantumA Please read the new hint.
  $endgroup$
  – Robert Z
  Mar 1 at 16:02
  

  
  
  
  

add a comment | 

$begingroup$

Hint 1. As regards the asymptotic analysis (complexity?), you may use the Master Theorem. Then $c_crit=log_2(3)approx 1.58$ and $f(n)=fracn^1/2log(n)leq n^1/2$. What about $T(n)$?

Hint 2. Note that
$$t(2^n)=3^nt(1)+sum_k=0^n-1frac3^ksqrt2^n-klog (2^n-k)
=3^nt(1)+3^nsum_k=1^nfrac(sqrt2/3)^kklog (2)sim Ccdot 3^n$$
because the series $sum_k=1^nfrac(sqrt2/3)^kklog (2)$ is convergent (note that $sqrt2/3<1$).

share|cite|improve this answer

edited Mar 2 at 14:33

answered Mar 1 at 6:56

Robert ZRobert Z

101k1069142

$endgroup$

share|cite|improve this answer

edited Mar 2 at 14:33

answered Mar 1 at 6:56

Robert ZRobert Z

101k1069142

answered Mar 1 at 6:56

Robert ZRobert Z

101k1069142

answered Mar 1 at 6:56

Robert ZRobert Z

101k1069142

1

$begingroup$

$$
t(2^log_2 n) = 3 tleft(2^log_2left(frac u2right)right)+fracsqrt nln n
$$

now calling $T(u) = t(2^u)$ with $u = log_2 n$ we follow with

$$
T(u) = 3T(u-1) + frac2^frac u2uln 2
$$

This is a linear recurrence with solution $T(u) = T_h(u) + T_p(u)$

$$
begincases
T_h(u) = 3T_h(u-1) \
T_p(u) = 3T_p(u-1) + frac2^frac u2uln 2
endcases
$$

For the homogeneous we have

$$
T_h(u) = C_0 3^u
$$

and now making $T_p(u) = C_0(u) 3^u$ and substituting we have

$$
C_0(u)-C_0(u-1) = 3^-ufrac2^frac u2uln 2 = frac1lambdafracalpha^uu
$$

with $alpha = fracsqrt 23 < 1$ and $lambda = ln 2$

so we have

$$
C_0(u) = frac1lambdasum_k=1^ufracalpha^kk
$$

and then

$$
T(u) = left(C_0+frac1lambdasum_k=1^ufracalpha^kkright)3^u
$$

hence

$$
t(n) = left(C_0 + frac1ln 2sum_k=1^log_2 nfracalpha^kkright)3^log_2 n
$$

share|cite|improve this answer

answered Mar 12 at 8:27

CesareoCesareo

9,3963517

$endgroup$

add a comment | 

1

$begingroup$

$$
t(2^log_2 n) = 3 tleft(2^log_2left(frac u2right)right)+fracsqrt nln n
$$

now calling $T(u) = t(2^u)$ with $u = log_2 n$ we follow with

$$
T(u) = 3T(u-1) + frac2^frac u2uln 2
$$

This is a linear recurrence with solution $T(u) = T_h(u) + T_p(u)$

$$
begincases
T_h(u) = 3T_h(u-1) \
T_p(u) = 3T_p(u-1) + frac2^frac u2uln 2
endcases
$$

For the homogeneous we have

$$
T_h(u) = C_0 3^u
$$

and now making $T_p(u) = C_0(u) 3^u$ and substituting we have

$$
C_0(u)-C_0(u-1) = 3^-ufrac2^frac u2uln 2 = frac1lambdafracalpha^uu
$$

with $alpha = fracsqrt 23 < 1$ and $lambda = ln 2$

so we have

$$
C_0(u) = frac1lambdasum_k=1^ufracalpha^kk
$$

and then

$$
T(u) = left(C_0+frac1lambdasum_k=1^ufracalpha^kkright)3^u
$$

hence

$$
t(n) = left(C_0 + frac1ln 2sum_k=1^log_2 nfracalpha^kkright)3^log_2 n
$$

share|cite|improve this answer

answered Mar 12 at 8:27

CesareoCesareo

9,3963517

$endgroup$

add a comment | 

$begingroup$

$$
t(2^log_2 n) = 3 tleft(2^log_2left(frac u2right)right)+fracsqrt nln n
$$

now calling $T(u) = t(2^u)$ with $u = log_2 n$ we follow with

$$
T(u) = 3T(u-1) + frac2^frac u2uln 2
$$

This is a linear recurrence with solution $T(u) = T_h(u) + T_p(u)$

$$
begincases
T_h(u) = 3T_h(u-1) \
T_p(u) = 3T_p(u-1) + frac2^frac u2uln 2
endcases
$$

For the homogeneous we have

$$
T_h(u) = C_0 3^u
$$

and now making $T_p(u) = C_0(u) 3^u$ and substituting we have

$$
C_0(u)-C_0(u-1) = 3^-ufrac2^frac u2uln 2 = frac1lambdafracalpha^uu
$$

with $alpha = fracsqrt 23 < 1$ and $lambda = ln 2$

so we have

$$
C_0(u) = frac1lambdasum_k=1^ufracalpha^kk
$$

and then

$$
T(u) = left(C_0+frac1lambdasum_k=1^ufracalpha^kkright)3^u
$$

hence

$$
t(n) = left(C_0 + frac1ln 2sum_k=1^log_2 nfracalpha^kkright)3^log_2 n
$$

share|cite|improve this answer

answered Mar 12 at 8:27

CesareoCesareo

9,3963517

$endgroup$

share|cite|improve this answer

answered Mar 12 at 8:27

CesareoCesareo

9,3963517

answered Mar 12 at 8:27

CesareoCesareo

9,3963517

answered Mar 12 at 8:27

CesareoCesareo

9,3963517