Question

which one of the following correctly determines the solution of the reccurence relation with T(1)=1. T(n)=2T(n2)+logn​

Answer 1

Answer:

Masters Theorem, we know that for T(n) = aT(n/b) + O(nklogPn), if a > bk

T(n) = θ(n^(logba))

In this question, we have a = b = 2, and k = 0, so we get a > bk, which gives us T(n) = θ(n).