Algorithms and recursion?

Question

I have the following recursion: T (n) = 2 * T (n / 4) + T (n / 2) + n, and I need to know the exact equation, I know that Teacher’s theorem will not help me, and the iteration seems wrong ...

Please tell us how to do this in general for such recursions. Thanks in advance.

Hi everyone, thanks for the answer, I need complexity. I need to understand how to solve such problems.

Answer 1

T(n) = O(nlogn) and W(nlogn)

To prove that, by the definition of O we need to find the constants n0 and c such that: for each n>=n0 , T(n)<=cnlogn .

We will use induction on n to prove that T(n)<=cnlogn for all n>=n0

Now skip the base register ... (we'll come back later)

Hypothesis: Assume that for each k<n , T(k)<=cklogk

Thesis: We want to prove that T(n)<=cnlogn

But T(n)=2T(n/4)+T(n/2)+n

Using the hypothesis, we get:

T(n)<=2(c(n/4)log(n/4))+c(n/2)log(n/2)+n=cnlogn + n(1-3c/2)

So, taking c>=2/3 T(n)<=cnlogn will prove our thesis, because then T(n)<=cnlogn

Now we need to prove the base case:

We take n0=2 , because if we take n0=1 , then logn will be 0 , and this will not work with our thesis. So our base cases would be n=2,3,4 . We need the following statements:

T(2) <= 2clog2

T(3) <= 3clog3

T(4) <= 4clog4

So, taking c=max{2/3, T(2)/2, T(3)/3log3, T(4)/8} and n0=2 , we find constants c and n0 such that for any natural n>=n0 , T(n)<=cnlogn

The demonstration for T(n) = W(nlogn) is analog.

So, basically, in those cases when you cannot use the theorem of the Master, you need to "guess" the result and prove it by induction.

For more information about these demos, see "Introduction to Algorithms"

Answer 2

First of all, you need to define some restrictions on this, otherwise it will never end and you will encounter an OverflowException. Something like n is an integer, and the minimum value is 0.

Could you tell us more about your question in this way?

Answer 3

This does not help you figure out how to do this, but apparently Wolfram Alpha might get the right answer. Perhaps you can find the documentation or Mathematica to show you the steps that it takes to resolve this issue:

Wolfram Alpha: T(n)=2*T(n/4)+T(n/2)+n

To put rough upper and lower bounds in the search space, you could recognize that your T (n) is bounded higher by 3T (n / 2) + n and lower by 2T (n / 4) + n ... so O (n ^ (3/2)) and W (n), by the main theorem.

In the general case, solving recurrence relationships is a tough task.