This problem is on recurrence relations. (a) You are given a divide-and-conquer

Question

This problem is on recurrence relations. (a) You are given a divide-and-conquer algorithm. Algorithm A. The running time of Algorithm A is T(n) = Theta(n^2). You are also told that, in the DIVIDE step, Algorithm A does some work that leads to three subproblems (which it then solves recursively). Write down a possible recurrence for the running time of Algorithm A. Justify your answer by solving your recurrence and showing that the solution is indeed T(n) = Theta(n^2). (b) Your friend has designed a search algorithm, and she tells you that the algorithm's running time is given by the recurrence T(n) = T([Squareroot n]) +1, for n > 1, and T(1) = 1. For a certain problem, you are trying to decide between using your friend's algorithm and binary search. If asymptotic running time is your only criterion in making this decision, which algorithm would you choose? Justify your answer.

Explanation / Answer

1) By statements we came to know that

T(n) = O(n2)

and we break the problem into three subproblem of size n/2 each

=> 3T(n/2) + f(n)

All will depend on f(n) , Lets find f(n) by taking help of T(n) i.e n2

Masters theorem = > a = 3 , b = 2
=> nlog3 2 = n0.63

Since c*f(n) >= nlog3 2

=> f(n) =  n2 and By case 1 of masters theorem we infer

Hence T(n) = 3T(n/2) + cn2

2)

T(n) = T(|sqrt(n)|) +1.

Let us assume n= 2m

Now , above recurrence becomes T(2m) = T(2m/2) +1.

Lets assume T(2m) = S(m) , where S is some function of m.

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

Use masters theorem with a =1 , b = 2 => nlog 21  = n0 = 1
Case 2 : f(n) = 1 => O(m0 log m)

we get S(m) = log(m).

Also we had assume n=2m,

and T(n) =S(log(n)) = log( log (n) ).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.