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

  • 2
    What is $\theta(n)?$2011-07-04
  • 0
    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)2011-07-04
  • 0
    Is $n$ supposed to be an integer (in which case $\frac{n}{4}$ is not always one)?2011-07-04
  • 0
    yes, It is a big integer that can be divided by 4 until it reaches 1.2011-07-04
  • 0
    To be honest, Originally I posted this question in StackOverFlow but they argued that it belongs to here, Eventhough I'm not sure it is.2011-07-04
  • 1
    @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).2011-07-04
  • 0
    I think if $T$ is positive and increasing on $(0,\infty)$, then its rate of growth is somewhere between $\log n$ and $\sqrt{n}$.2011-07-04
  • 1
    Are you given termination conditions?2011-07-05
  • 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.

  • 0
    I didn't understand what is your conclusion.2011-07-04
  • 0
    Well, for example, the constant function is not bounded from the bottom by 'n'.2011-07-04
  • 1
    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.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$.