Question

r the recurrence relation o. Consider T(n) = Vn T(Vn) + n a. Why can't you solve this with the master theorem? b. S t involves a constant C, tell me what it is in terms of T(O), T(1), or whatever your inequality by induction. Show the base case. Then show the how that T( n)= 0(n lg ig n). First, clearly indicate the inequality that you wish to hen proceed to prove the inductive hypothesis inductive case, and clearly indicate where you use

Answer 1

a) We cannot apply Master Theorem in this. as it is not of the form

T(n) = aT(n/b) + f(n)

a is √n here , Hence it is not of the form, So we cannot apply Masters theorem on this

b) T(n) = √nT(√n) + n

Divide by n we get
T(n)/ n = T(√n)/ √n) + 1

Let n = 2^m

T(2^m )/ 2^m   = T(2^m/2)/ 2^m/2 + 1

S(m) = T(2^m) / 2^m

S(m) = S(m/2) + 1

Solving the above we get S(m) = O(logm)
Substituting we get T(n)/n = log logn

=> T(n) = O(n log(logn))


Thanks, PLEASE COMMENT if there is any concern. PLEASE UPVOTE