0

I need solve this recursion: $$T(n) = T(\alpha n)+T(\beta n)+\gamma n$$ I know that for $\alpha +\beta< 1$ solution is $O(n)$

How is for $\alpha + \beta = 1$ and $\alpha + \beta > 1$?

Edison91
  • 1
  • 1
    Are there any theorems at your disposal? What are your thoughts? It is important to give as much context as possible so that users can best formulate their answers. –  Feb 03 '16 at 22:51
  • To solve this problem we can use recursion tree. For α+β<1 I saw some lecture. For α+β=1 I've just found solution but how is about α+β>1? http://homepages.math.uic.edu/~jan/mcs360/recursion_tree_method.pdf – Edison91 Feb 03 '16 at 22:55
  • For $\alpha+\beta > 1$, are you sure this is well-defined? (at least, ask that $\alpha < 1$ and $\beta < 1$) – Clement C. Feb 03 '16 at 22:56
  • What are the conventions here: $T$ is defined for real numbers? Or if defined for integers, what to do when $\alpha n$ is not an integer? – GEdgar Feb 03 '16 at 22:56
  • @Clement C. You are right. So 1<α+β<2 – Edison91 Feb 03 '16 at 23:01
  • @GEdgar I's cost of algorithm – Edison91 Feb 03 '16 at 23:03
  • Generally "solve recursion" means to write a function non recursively. What you are asking for is the asymptotic behavior of a function, completely different. – DanielV Feb 03 '16 at 23:06
  • My fault. I want sth like this http://courses.csail.mit.edu/6.046/spring04/handouts/prac-quiz1-sol.pdf page 3 – Edison91 Feb 03 '16 at 23:10
  • Or here is better explanation http://stackoverflow.com/questions/28090361/recursive-tree-with-constant-tn-tn-3-t2n-3-cn – Edison91 Feb 03 '16 at 23:13

2 Answers2

0

Take a look at Leighton's "Notes on Better Master Theorems for Divide-and-Conquer Recurrences" (1996).

Martin Sleziak
  • 53,687
vonbrand
  • 27,812
0

Normally if you suspect something you should simply substitute it $T(n)=knG(n)$. So we have

$$knG(n)=kn\alpha G(\alpha n)+kn\beta G(\beta n) + \gamma n$$

and this gives

$$G(n)=\alpha G(\alpha n)+\beta G(\beta n) + \frac{\gamma}{k}$$

This recursion cannot have any other solution than constant (if it is to have any solution at all) $G(n)=c$ and it is even strict what constant it must be

$$c=\frac{\gamma}{k(1-\alpha-\beta)}$$

If $\alpha + \beta = 1$ then it must be $\gamma = 0$ if we want to have at least one solution.

So the solution is

$$ T(n)=n\frac{\gamma}{1-\alpha-\beta}, \; \alpha+\beta \neq 1 $$ $$ T(n)=kn, \; \alpha+\beta = 1, \; \gamma = 0 $$

This makes it $O(n)$ whatever it takes but you cannot neglect restrictions, if you want to have any solution, and in the case $\alpha+\beta = 1$ although still linear $k$ can be as large as you like. Similar if $\alpha+\beta$ is very close to 1.