Question

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?

T(n) = 2T($\frac{n}{2}$) + log n

• A. $\Theta$(n)
• B. $\Theta$$n^2$
• C. $\Theta$(log n)
• D. $\Theta$(n log n)

Answer 1

The correct option is A $\Theta$(n)

T(n) = 2T(n/2) + log n
[by master theorem case 1]
= $\Theta$(n)