Dgdrxrt

Button changing it's text & action. Good or terrible?

Can someone be penalized for an "unlawful" act if no penalty is specified?

Apparent duplicates between Haynes service instructions and MOT

slides for 30min~1hr skype tenure track application interview

How to type this arrow in math mode?

If a Druid sees an animal’s corpse, can they wild shape into that animal?

Is this app Icon Browser Safe/Legit?

Can a rogue use sneak attack with weapons that have the thrown property even if they are not thrown?

Is a "Democratic" Oligarchy-Style System Possible?

Pokemon Turn Based battle (Python)

How to answer pointed "are you quitting" questioning when I don't want them to suspect

Why not take a picture of a closer black hole?

How to manage monthly salary

Are there any other methods to apply to solving simultaneous equations?

Deal with toxic manager when you can't quit

Why can Shazam fly?

Is three citations per paragraph excessive for undergraduate research paper?

What do hard-Brexiteers want with respect to the Irish border?

If I score a critical hit on an 18 or higher, what are my chances of getting a critical hit if I roll 3d20?

Have you ever entered Singapore using a different passport or name?

What is the accessibility of a package's `Private` context variables?

Shouldn't "much" here be used instead of "more"?

What do the Banks children have against barley water?

Are there incongruent pythagorean triangles with the same perimeter and same area?

solving a recurrence equation $T(n) = T(cn) + T((1-c)n) + 1$

1

1

$begingroup$

first, this question has been asked here before, however I have some issues with it that haven't been answered yet :

give asymptotic bounds of $ T(n) $ where

$ T(n) = T(cn)+ T((1-c)n) +1 , 0<c<1 $

this is the original post link
I didn't quite understand why the answer given over there was with a linear solution $S(n) = nS(1)$

and another thing, I've been told by someone that an even tighter bound is $theta(log(n))$ is possible.

so two things, is this true, and why is the linear solution is of the form given before.

thanks ahead.

recurrence-relations asymptotics

share|cite|improve this question

edited Apr 1 at 14:48

user

6,46311031

asked Mar 30 at 17:27

lidor718lidor718

175

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The title has $+1$ on the rhs, the body has $+n$. The Akra–Bazzi method is applicable to both cases, giving $p = 1$.
  $endgroup$
  – Maxim
  Apr 1 at 13:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It’s suppose to be +1
  $endgroup$
  – lidor718
  Apr 1 at 13:45
  

  
  
  
  

add a comment | 

1

1

$begingroup$

first, this question has been asked here before, however I have some issues with it that haven't been answered yet :

give asymptotic bounds of $ T(n) $ where

$ T(n) = T(cn)+ T((1-c)n) +1 , 0<c<1 $

this is the original post link
I didn't quite understand why the answer given over there was with a linear solution $S(n) = nS(1)$

and another thing, I've been told by someone that an even tighter bound is $theta(log(n))$ is possible.

so two things, is this true, and why is the linear solution is of the form given before.

thanks ahead.

recurrence-relations asymptotics

share|cite|improve this question

edited Apr 1 at 14:48

user

6,46311031

asked Mar 30 at 17:27

lidor718lidor718

175

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The title has $+1$ on the rhs, the body has $+n$. The Akra–Bazzi method is applicable to both cases, giving $p = 1$.
  $endgroup$
  – Maxim
  Apr 1 at 13:24
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It’s suppose to be +1
  $endgroup$
  – lidor718
  Apr 1 at 13:45
  

  
  
  
  

add a comment | 

$begingroup$

first, this question has been asked here before, however I have some issues with it that haven't been answered yet :

give asymptotic bounds of $ T(n) $ where

$ T(n) = T(cn)+ T((1-c)n) +1 , 0<c<1 $

this is the original post link
I didn't quite understand why the answer given over there was with a linear solution $S(n) = nS(1)$

and another thing, I've been told by someone that an even tighter bound is $theta(log(n))$ is possible.

so two things, is this true, and why is the linear solution is of the form given before.

thanks ahead.

recurrence-relations asymptotics

share|cite|improve this question

edited Apr 1 at 14:48

user

6,46311031

asked Mar 30 at 17:27

lidor718lidor718

175

$endgroup$

share|cite|improve this question

edited Apr 1 at 14:48

user

6,46311031

asked Mar 30 at 17:27

lidor718lidor718

175

share|cite|improve this question

edited Apr 1 at 14:48

user

6,46311031

asked Mar 30 at 17:27

lidor718lidor718

175

edited Apr 1 at 14:48

user

6,46311031

edited Apr 1 at 14:48

user

6,46311031

asked Mar 30 at 17:27

lidor718lidor718

175

asked Mar 30 at 17:27

lidor718lidor718

175