Let T(n) be the function defined by T(n) = 1 and T(n) = 2T (n/2) + n, which of the following is TRUE ?

Question

A.    T(n) = $O( n Log n)$
B.    T(n) = $O({(logn)}^2)$
C.    T(n) = $O(n)$
D.    T(n) = $O(n^2)$

Answer 1

Dude Its a simple Merge Sort algorithm, reccurance relation. 

Answer will be A) $O(nLogn)$

Well Here you can check the solution, if you want. 

Comments

ok

---

Using master’s theorem also can apply and ans is O(n logn).