21k 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?
8k views

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

How to solve the recurrence $T(n) = T(n/2) + T(n/4) + T(n/8)$? [duplicate]

How to solve the recurrence $T(n) = T(n/2) + T(n/4) + T(n/8)$? We assume that $T(n)$ is constant for sufficiently small $n$.
2k views

Recurrence Problem $T(n) = 3T(n/3) + n$ [duplicate]

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

Solving this recurrence: T(n) = 9 T(n/2) + n^3 lg n [duplicate]

Would it be possible to use the master theorem to solve the following recurrence? T(n) = 9 T(n/2) + n^3 lg n This recurrence hasn't been mentioned before in any of the questions on StackOverflow. ...
2k 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 ...