Let $T(n)$ be defined recursively by
$$T(1) = 4 $$
$$T(n) = 2T(\frac n2) +5n,\qquad n\geq 2 $$
Prove T(n) is = O(n*log(n), Log is always base 2, so Log base2 (n)
T(n) <= C * n * log(n) for all n >= k Im using k = 2 and c = 9
Base Case 2: 2 * T(1) + 5 * 2 <= 9 * 2 * log(2) 18 <= 18 = Big O
Assume n = k
Assume 2 * T(n/2) + 5 * n <= 9 * n * log(n)
How do I finish the proof for n+1
Thanks for any input, all help is wanted
Suppose the recurrence is $T(n) = aT(n/a) +bn$ and $T(m) < c m \lg m$ for all $2 \le m < n$.
Then
$\begin{array}\\ T(n) &\lt a c(n/a)\lg(n/a)+bn\\ &= cn(\lg(n)-\lg(a))+bn\\ &= cn\lg(n)-cn\lg(a)+bn\\ &= cn\lg(n)+n(b-c\lg(a))\\ &< cn\lg(n) \qquad\text{if }c > b/\lg(a)\\ \end{array} $
Therefore, by choosing $c > \max(b/\lg a, \max(T(j)/(j \lg j), j=2\ to\ m))$, $T(n) < cm\lg n$ for $n > m$ so $T(n) = O(n \lg n)$.