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

$\endgroup$
  • 2
    $\begingroup$ What is $\theta(n)?$ $\endgroup$ – Eric Naslund Jul 4 '11 at 20:21
  • $\begingroup$ 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) $\endgroup$ – user6163 Jul 4 '11 at 20:24
  • $\begingroup$ Is $n$ supposed to be an integer (in which case $\frac{n}{4}$ is not always one)? $\endgroup$ – Joel Cohen Jul 4 '11 at 20:35
  • 1
    $\begingroup$ @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). $\endgroup$ – Eric Naslund Jul 4 '11 at 21:28
  • 1
    $\begingroup$ Are you given termination conditions? $\endgroup$ – kuch nahi Jul 5 '11 at 0:35
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I didn't understand what is your conclusion. $\endgroup$ – user6163 Jul 4 '11 at 20:55
  • $\begingroup$ Well, for example, the constant function is not bounded from the bottom by 'n'. $\endgroup$ – Mark Bennet Jul 4 '11 at 21:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark Bennet Jul 5 '11 at 5:12
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy