UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 21)

UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 21)

 Q21. The solution of the recurrence relation

            T(m) = T(3m/4) + 1 is:

(1). θ (lg m)                                                  (2). θ (m)

(3). θ (mlg m)                                               (4). θ (lglg m)


Answer : (1). θ (lg m)    

Master theorem (analysis of algorithms)

The master theorem sometimes yields asymptotically tight bounds to some recurrences from divide and conquer algorithms that partition an input into smaller sub-problems of equal sizes, solve the sub-problems recursively, and then combine the sub-problem solutions to give a solution to the original problem. The time for such an algorithm can be expressed by adding the work that they perform at the top level of their recursion (to divide the problems into sub-problems and then combine the sub-problem solutions) together with the time made in the recursive calls of the algorithm. If T(n) denotes the total time for the algorithm on an input of size n and f(n)  denotes the amount of time taken at the top level of the recurrence then the time can be expressed by a recurrence relation that takes the form: 

 So, according to master theorem the run-time of the above algorithm can be expressed as:

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

where  n = size of the problem

     a = number of sub-problems in the recursion and a >= 1

     n/b = size of each sub-problem

     f(n) = cost of work done outside the recursive calls like dividing into sub-problems 

                 and cost of combining them to get the solution. 

T(n) = aT(n/b) + θ (n^k log^p n)

where n = size of the problem
a = number of sub-problems in the recursion and a >= 1
n/b = size of each sub-problem
b > 1, k >= 0 and p is a real number.
Then,

1. if a > b^k, then T(n) = θ(n^log_ba)


2. if a = b^k, then
   (a) if p > -1, then T(n) = θ(n^log_ba log^p+1n)
   (b) if p = -1, then T(n) = θ(n^log_ba loglogn)
   (c) if p < -1, then T(n) = θ(n^log_ba)


3. if a < b^k, then
   (a) if p >= 0, then T(n) = θ(n^k log^pn)
   (b) if p < 0, then T(n) = θ(n^k) 

 Solution:

where         a = 1,           b = 4/3,        k = 0,    p = 0

Here k = 0 and p = 0 , p > -1
from a = b^k  , where k = 0,  So   a = 1,  also b = 1 Therefore a = b
Now we have p > -1

then T(m) = θ(m^{log _b a} log ^p+1 m)

 We also have b = 4/3,  a = 1, p = 0

T(m) = θ(m^(log_4/3)0 log⁰⁺¹ m)

T(m) =  θ(m^{log _4/3 0} log⁰⁺¹ m)

T(m) =  θ(m⁰ log¹m)

T(m) =  θ( log m )