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