Question

Show that the solution of T(n) = 2T( ën/2û ) + n is W(n lg n). Conclude that the solution is Q(n lg n).

Answer 1

Solution for the problem is provided below, please comment if any doubts:

Here we need to prove that the solution of T(n) = 2T( n/2) + n is O(n lg n)

We can prove this using substitution method,

For T(n)=O(n lg n), there must exists a constant “c” such that T(n) ≤ c (n lg n)

Induction hypothesis is assume that “T(n) ≤ c (n lg n)” all numbers less than n

Now, T((n/2)) ≤ 2c (n/2) lg (n/2)+n

       ≤ cn lg (n/2)+n = cn ( lg n – lg 2)+n = cn ( lg n – 1)+n

            =cn lg n – cn +n

cn lg n – cn +n ≤ cn lg n, for c>1

That is for c>1 T(n) ≤ c (n lg n)

That is T(n)=O(n lg n)