Linked Questions

According to Introduction to algorithms by Cormen et al, $$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why? And which case of master theorem is it?

What is the complexity of the follwoing recurrence? $$T(n) = T(n-1) + 1/n$$ I highly suspect the answer to be $O(1)$, because your work reduces by $1$ each time, so by the $n$th time it would be $T(n-...

How can one solve $$T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log n$$ without using the master method? I know it has a solution using the master theorem from this link.

Possible Duplicate: Solving or approximating recurrence relations for sequences of numbers I know that the solution for $T(n) = 2 T(n/2) + O(n)$ is $ T(n) = O(n \log(n))$ But how do you get to ...

I've been learning master theorem in school now and have learnt how to apply it to a number of recurrence relations. However one of my assignments has the following recurrence relation: T(n) = T(n-2) ...

I'm currently in a course, and I for the life of me cannot figure out what my professor is doing. I could really use a working example, and I was hoping someone here might oblige. Suppose we have ...

This is a question about recurrence relation that contains sum inside the recursion.I am totally stuck. Can anyone help? The problem asks to solve the following recursion $T(n)=\frac{1}{n} \sum_{i=1}^...

I'm trying to solve the recurrence relation T(n) = 3T(n-1) + n and I think the answer is O(n^3) because each new node spawns three child nodes in the recurrence tree. Is this correct? And, in terms of ...

Problem statement: Solve $T(n)$ for $T(n)=2T(n-1)+n$, $n > 1$, and $T(1)=1$. My attempt: I tried back substituting but I am unable to find a general pattern: $$\begin{align*} T(n) &=2^2 T(n-2)...

I really need help to solve the following: T(n)=T(n-a)+n where a is a constant greather or equal 1. So I started to iterate T(n)=T(n-a)+n =T(((n-a)+n)-a)+n =T(3n-3a)+n =T(((3n-3a)+n)-...

I was reading dynamic programming chapter from famous book Introduction To Algorithm In rod cutting problem it gives simple algorithm as follows: ...

Solve the following recurrence equations a. T(n) = T(n/2) + 18 b. T(n) = 2T(n/2) + 5n c. T(n) = 3T(n/2) + 5n d. T(n) = T(n/2) + 5n This is only a sample of what I was given but I am not sure what ...

I've searched online for this but I only seem to find answers for a similar equation: T(n) = T(n/3) + T(2n/3) + cn But the one I'm trying to solve is: ...

My question here is dealing with the residual that I get. We are trying to prove $T(n) = 3T(n/3) + n$ is $O(n*\log n)$. So where I get is $T(n) \le cn[\log n - \log 3] + n$. So my residual is $-cn\log ...

For instance, consider the following recurrence relation. T(n) = T(n/2) + T(n/3) + T(n/4) + n Would you use the substitution method for this?