Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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
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). –  Eric Naslund Jul 4 '11 at 21:28
1  
Are you given termination conditions? –  kuch nahi Jul 5 '11 at 0:35
show 4 more comments

3 Answers 3

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.

share|improve this answer
    
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
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. –  Mark Bennet Jul 5 '11 at 5:12
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.