2
$\begingroup$

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

  • 0
    The next natural question is to ask for $\lim_{n \to \infty} T(n)/n$. Since $n/4$ and $3n/4$ are not necessarily integers this depends on how you round; the correct way to do this presumably comes from the algorithm that gives rise to this recurrence. But it appears that for any combination of rounding up, rounding down, and rounding to the nearest integer that limit doesn't exist; rather $T(n)/n$ oscillates between two constants $a$ and $b$.2011-07-05

3 Answers 3

4

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.

  • 1
    Sorry that was$n$'t a very good comme$n$t - but what I meant was that the order of growth was not determined by the information you gave because there is this constant solution.2011-07-05
2

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.

2

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$.