# Recursion equations: $T(n)=T(\frac{n}{4})+T(\frac{3}{4}n)+1$

What's the simplest way to prove that the solution for this recursion equation: $T(n)=T(\frac{n}{4})+T(\frac{3}{4}n)+1$ ,

is $T(n)=\theta (n)$?

I think that it is $T(n)=\theta (n)$ because it is just +1 in every iteration and it looks like it will do that n times, but I'm not sure.

Thank you

• What is $\theta(n)?$ – Eric Naslund Jul 4 '11 at 20:21
• Theta Notation For non-negative functions, f(n) and g(n), f(n) is theta of g(n) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). This is denoted as "f(n) = Θ(g(n))". This is basically saying that the function, f(n) is bounded both from the top and bottom by the same function, g(n). (WIKIPEDIA) – user6163 Jul 4 '11 at 20:24
• Is $n$ supposed to be an integer (in which case $\frac{n}{4}$ is not always one)? – Joel Cohen Jul 4 '11 at 20:35
• @Nir: If you meant theta notation you should write $\Theta(n)$, not $\theta(n)$. In tex, the difference is \Theta(n) rather than \theta(n). – Eric Naslund Jul 4 '11 at 21:28
• Are you given termination conditions? – kuch nahi Jul 5 '11 at 0:35

Well if $T(n) = \alpha n + \beta$, I reckon $\beta=-1$ and $\alpha$ is arbitrary.

So there is at least:

1. The constant solution $T(n) = -1$ for all n

2. The solution $T(n) = \alpha n -1$ for all n and for any non-zero $\alpha$

And these two solutions have different orders.

• I didn't understand what is your conclusion. – user6163 Jul 4 '11 at 20:55
• Well, for example, the constant function is not bounded from the bottom by 'n'. – Mark Bennet Jul 4 '11 at 21:00
• Sorry that wasn't a very good comment - but what I meant was that the order of growth was not determined by the information you gave because there is this constant solution. – Mark Bennet Jul 5 '11 at 5:12

Assuming that you are talking about time complexity (hence positive and non-decreasing), Akra-Bazzi does indeed give us that $T(n) = \Theta(n)$. You might even be able to do away with the non-decreasing condition to apply Akra-Bazzi, not sure.

There are solutions that are not $\Theta(n)$. For example, if $z = s + i t$ is a complex number such that $1 = (1/4)^z + (3/4)^z$, then $T(n) = -1 + a (n^z + n^{\overline{z}}) = -1 + 2 a n^s \cos(t \ln n)$ is a solution. An example of such $z$ is approximately $-0.28834269920979211732 +3.7873005856456993583 i$.