Fdtxjr

Area of a 2D convex hull

How can you insert a "times/divide" symbol similar to the "plus/minus" (±) one?

Can a non-EU citizen traveling with me come with me through the EU passport line?

How does modal jazz use chord progressions?

3 doors, three guards, one stone

What computer would be fastest for Mathematica Home Edition?

Is drag coefficient lowest at zero angle of attack?

If A makes B more likely then B makes A more likely"

What loss function to use when labels are probabilities?

Why does tar appear to skip file contents when output file is /dev/null?

Antler Helmet: Can it work?

How is simplicity better than precision and clarity in prose?

Is it possible to ask for a hotel room without minibar/extra services?

Was credit for the black hole image misattributed?

Blender game recording at the wrong time

Why use gamma over alpha radiation?

Is there a service that would inform me whenever a new direct route is scheduled from a given airport?

Typsetting diagram chases (with TikZ?)

When is phishing education going too far?

Can a zero nonce be safely used with AES-GCM if the key is random and never used again?

Stop battery usage [Ubuntu 18]

What do you call the holes in a flute?

What did Darwin mean by 'squib' here?

Did the new image of black hole confirm the general theory of relativity?

Solve recurrence relation for non trivial base case

1

1

$begingroup$

As per the title, I'm having some trouble to solve the recurrence equation

Edited

$$ T(N) = 2T left(leftlceil fracN+12 rightrceilright) + 2T left(leftlfloor fracN+12 rightrfloorright)$$
which is true for $N > 4$. I have two base cases, $T(3) = 6$ and $T(4) = 18$, but I'm stuck on how to proceed.

recurrence-relations

share|cite|improve this question

edited Mar 26 at 7:49

tigerjack89

asked Mar 25 at 21:04

tigerjack89tigerjack89

889

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Your base cases are contradictory. $T(3)=4T(2)$ and $T(4)=4T(2)$ so $T(3)=T(4)$ but this is not true.
  $endgroup$
  – Peter Foreman
  Mar 25 at 21:20
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Yeah, sorry it's fine now.
  $endgroup$
  – Peter Foreman
  Mar 25 at 22:25
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  You mentioned $n^2 ln n$, are you interested in the asymptotic behavior of $T(n)$? It is in fact $Theta(n^2)$ by the master theorem.
  $endgroup$
  – Maxim
  Mar 27 at 21:48
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Maxim thanks, it is surely better than nothing. But it could be great to also show the exact solution (constants throws in) or at least an approximation of it. Of course I'm also interested in the explanation (which in the case of master theorem is obvious).
  $endgroup$
  – tigerjack89
  Mar 28 at 6:41
  

  
  
  
  

add a comment | 

1

1

$begingroup$

As per the title, I'm having some trouble to solve the recurrence equation

Edited

$$ T(N) = 2T left(leftlceil fracN+12 rightrceilright) + 2T left(leftlfloor fracN+12 rightrfloorright)$$
which is true for $N > 4$. I have two base cases, $T(3) = 6$ and $T(4) = 18$, but I'm stuck on how to proceed.

recurrence-relations

share|cite|improve this question

edited Mar 26 at 7:49

tigerjack89

asked Mar 25 at 21:04

tigerjack89tigerjack89

889

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Your base cases are contradictory. $T(3)=4T(2)$ and $T(4)=4T(2)$ so $T(3)=T(4)$ but this is not true.
  $endgroup$
  – Peter Foreman
  Mar 25 at 21:20
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Yeah, sorry it's fine now.
  $endgroup$
  – Peter Foreman
  Mar 25 at 22:25
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  You mentioned $n^2 ln n$, are you interested in the asymptotic behavior of $T(n)$? It is in fact $Theta(n^2)$ by the master theorem.
  $endgroup$
  – Maxim
  Mar 27 at 21:48
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Maxim thanks, it is surely better than nothing. But it could be great to also show the exact solution (constants throws in) or at least an approximation of it. Of course I'm also interested in the explanation (which in the case of master theorem is obvious).
  $endgroup$
  – tigerjack89
  Mar 28 at 6:41
  

  
  
  
  

add a comment | 

$begingroup$

As per the title, I'm having some trouble to solve the recurrence equation

Edited

$$ T(N) = 2T left(leftlceil fracN+12 rightrceilright) + 2T left(leftlfloor fracN+12 rightrfloorright)$$
which is true for $N > 4$. I have two base cases, $T(3) = 6$ and $T(4) = 18$, but I'm stuck on how to proceed.

recurrence-relations

share|cite|improve this question

edited Mar 26 at 7:49

tigerjack89

asked Mar 25 at 21:04

tigerjack89tigerjack89

889

$endgroup$

share|cite|improve this question

edited Mar 26 at 7:49

tigerjack89

asked Mar 25 at 21:04

tigerjack89tigerjack89

889

share|cite|improve this question

edited Mar 26 at 7:49

tigerjack89

asked Mar 25 at 21:04

tigerjack89tigerjack89

889

asked Mar 25 at 21:04

tigerjack89tigerjack89

889

asked Mar 25 at 21:04

tigerjack89tigerjack89

889

1 Answer
1

active

oldest

votes

2

+50

$begingroup$

For the simplicity put $T(n)=6S(n)$ for each $n$. Then the sequence $S$ satisfies the same recurrence relation. A computed graph of the function $S$ suggests that it is piecewise linear with bends at $n=2^k+1$ and $2^k+2^k-1+1$. Indeed, by induction we can show that $S(2^k+1)=4^k-1$ and $S(2^k+2^k-1+1)=3cdot 4^k-1$ for each $kge 1$. Also by induction we can show that between these points $S$ is linear, that is $$S(2^k+lambda 2^k-1+1)=(1+2lambda)4^k-1$$ and $$S(2^k+2^k-1+lambda 2^k-1+1)=(3+lambda)4^k-1$$ for each integer $2^k-1lambda$ between $0$ and $2^k-1$. The found form of the function $S$ easily implies bounds $frac 14letfracS(n) (n-1)^2le frac 13$ (and $tfrac 32(n−1)^2le T(n)le 2(n−1)^2$), for each $nge 3$.

share|cite|improve this answer

edited Apr 3 at 8:46

answered Mar 30 at 2:12

Alex RavskyAlex Ravsky

43.3k32583

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Sorry for the late response. Thanks for your help, I'm trying to understand your steps. Anyhow, how could one derive the asymptotic behaviour from this?
  $endgroup$
  – tigerjack89
  Apr 1 at 15:54
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Giving therefore $frac32(n-1)^2 leq T(n) leq 2(n-1)^2$, am I right?
  $endgroup$
  – tigerjack89
  Apr 3 at 8:34
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Well, I couldn't hope for a better bound!!! I'm still trying to figure out your method, but anyhow many thanks for your help. Would you add the last comments in your answer?
  $endgroup$
  – tigerjack89
  Apr 3 at 8:40
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks again for the help.
  $endgroup$
  – tigerjack89
  Apr 3 at 8:48
  

  
  
  
  

add a comment | 

Your Answer

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%2f3162321%2fsolve-recurrence-relation-for-non-trivial-base-case%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

+50

$begingroup$

For the simplicity put $T(n)=6S(n)$ for each $n$. Then the sequence $S$ satisfies the same recurrence relation. A computed graph of the function $S$ suggests that it is piecewise linear with bends at $n=2^k+1$ and $2^k+2^k-1+1$. Indeed, by induction we can show that $S(2^k+1)=4^k-1$ and $S(2^k+2^k-1+1)=3cdot 4^k-1$ for each $kge 1$. Also by induction we can show that between these points $S$ is linear, that is $$S(2^k+lambda 2^k-1+1)=(1+2lambda)4^k-1$$ and $$S(2^k+2^k-1+lambda 2^k-1+1)=(3+lambda)4^k-1$$ for each integer $2^k-1lambda$ between $0$ and $2^k-1$. The found form of the function $S$ easily implies bounds $frac 14letfracS(n) (n-1)^2le frac 13$ (and $tfrac 32(n−1)^2le T(n)le 2(n−1)^2$), for each $nge 3$.

share|cite|improve this answer

edited Apr 3 at 8:46

answered Mar 30 at 2:12

Alex RavskyAlex Ravsky

43.3k32583

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Sorry for the late response. Thanks for your help, I'm trying to understand your steps. Anyhow, how could one derive the asymptotic behaviour from this?
  $endgroup$
  – tigerjack89
  Apr 1 at 15:54
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Giving therefore $frac32(n-1)^2 leq T(n) leq 2(n-1)^2$, am I right?
  $endgroup$
  – tigerjack89
  Apr 3 at 8:34
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Well, I couldn't hope for a better bound!!! I'm still trying to figure out your method, but anyhow many thanks for your help. Would you add the last comments in your answer?
  $endgroup$
  – tigerjack89
  Apr 3 at 8:40
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks again for the help.
  $endgroup$
  – tigerjack89
  Apr 3 at 8:48
  

  
  
  
  

add a comment | 

2

+50

$begingroup$

For the simplicity put $T(n)=6S(n)$ for each $n$. Then the sequence $S$ satisfies the same recurrence relation. A computed graph of the function $S$ suggests that it is piecewise linear with bends at $n=2^k+1$ and $2^k+2^k-1+1$. Indeed, by induction we can show that $S(2^k+1)=4^k-1$ and $S(2^k+2^k-1+1)=3cdot 4^k-1$ for each $kge 1$. Also by induction we can show that between these points $S$ is linear, that is $$S(2^k+lambda 2^k-1+1)=(1+2lambda)4^k-1$$ and $$S(2^k+2^k-1+lambda 2^k-1+1)=(3+lambda)4^k-1$$ for each integer $2^k-1lambda$ between $0$ and $2^k-1$. The found form of the function $S$ easily implies bounds $frac 14letfracS(n) (n-1)^2le frac 13$ (and $tfrac 32(n−1)^2le T(n)le 2(n−1)^2$), for each $nge 3$.

share|cite|improve this answer

edited Apr 3 at 8:46

answered Mar 30 at 2:12

Alex RavskyAlex Ravsky

43.3k32583

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Sorry for the late response. Thanks for your help, I'm trying to understand your steps. Anyhow, how could one derive the asymptotic behaviour from this?
  $endgroup$
  – tigerjack89
  Apr 1 at 15:54
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Giving therefore $frac32(n-1)^2 leq T(n) leq 2(n-1)^2$, am I right?
  $endgroup$
  – tigerjack89
  Apr 3 at 8:34
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Well, I couldn't hope for a better bound!!! I'm still trying to figure out your method, but anyhow many thanks for your help. Would you add the last comments in your answer?
  $endgroup$
  – tigerjack89
  Apr 3 at 8:40
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks again for the help.
  $endgroup$
  – tigerjack89
  Apr 3 at 8:48
  

  
  
  
  

add a comment | 

$begingroup$

For the simplicity put $T(n)=6S(n)$ for each $n$. Then the sequence $S$ satisfies the same recurrence relation. A computed graph of the function $S$ suggests that it is piecewise linear with bends at $n=2^k+1$ and $2^k+2^k-1+1$. Indeed, by induction we can show that $S(2^k+1)=4^k-1$ and $S(2^k+2^k-1+1)=3cdot 4^k-1$ for each $kge 1$. Also by induction we can show that between these points $S$ is linear, that is $$S(2^k+lambda 2^k-1+1)=(1+2lambda)4^k-1$$ and $$S(2^k+2^k-1+lambda 2^k-1+1)=(3+lambda)4^k-1$$ for each integer $2^k-1lambda$ between $0$ and $2^k-1$. The found form of the function $S$ easily implies bounds $frac 14letfracS(n) (n-1)^2le frac 13$ (and $tfrac 32(n−1)^2le T(n)le 2(n−1)^2$), for each $nge 3$.

share|cite|improve this answer

edited Apr 3 at 8:46

answered Mar 30 at 2:12

Alex RavskyAlex Ravsky

43.3k32583

$endgroup$

share|cite|improve this answer

edited Apr 3 at 8:46

answered Mar 30 at 2:12

Alex RavskyAlex Ravsky

43.3k32583

answered Mar 30 at 2:12

Alex RavskyAlex Ravsky

43.3k32583

answered Mar 30 at 2:12

Alex RavskyAlex Ravsky

43.3k32583