13k views

### $T(n)=2T(n/2)+n\log n$ and the Master theorem [duplicate]

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?
4k views

1k views

### Algorithms - Solving recurrence-relations/Bounds? [duplicate]

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 ...
2k views

### Recurrence relation T(n) = 3T(n-1) + n [duplicate]

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 ...
756 views

### Solve recurrence T(n)=2T(n-1)+n for n greater than 1 and T(1)=1 [duplicate]

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)...
2k views

### recurrence - Iteration method T(n)=T(n-a)+n [duplicate]

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)-...
937 views

### Proving number of calls made in cut-rod algorithm [duplicate]

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

### Recurrence of T(n) = T(n/3) + T(2n/3) [duplicate]

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: ...
909 views

### How can I solve for T(n) recurrence equations? [duplicate]

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 ...
Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants. $T(n) = a$, if $n = 2$ $T(n) = 2T(n/2) + cn$ if $n > 2$ Use induction to prove ...