Induction proof for a recurrence relation in big O notation

Question

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

The problem is a bit flawed, since all you can say the result about is that $T(n) = O(n\log n)$ for $n=2^r$ with $r\in \Bbb Z^+ \cup 0$. — Mark Fischler, Feb 10 '18 at 17:42
Please have a look at the source code of my edit using the edit button, and try formatting the rest. — Arnaud Mortier, Feb 10 '18 at 17:43

score 1 · Answer 1 · answered Feb 10 '18 at 17:55

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)$.

Induction proof for a recurrence relation in big O notation

1 Answers1