UGC NET Computer Science July 2018 - II Question 21

Question 21

---

The solution of the recurrence relation
T(m) = T( 3m/4) + 1 is :

Options:

1. (1) θ (lg m)
2. (2) θ (m)
3. (3) θ (mlg m)
4. (4) θ (lglg m)

Answer : (1) θ (lg m)

Explanation Question 21

In this problem we use Master’s Theorem:
T(m)
= T(3m/4) + 1
= T(m/(4/3)) + 1

Now, compare above equation with below equation,
T(m) = aT(m/b) + n^klog^pn
then, we can get a = 1, b = 4/3, k = 0 and p = 0

Here, From above values we can conclude that we have to apply case 2 of Master's Theorem
a = 1 = b⁰ = b^k
∴ a=b^k

So, Apply case 2 of Master's Theorem
Here, p>-1,
∴ case 2 - (a) will be applicable from below master theorem.
∴ T(m) = θ( m^(log_ba)log^(p+1)m)

So, now after substituting values a=1, b=4/3, k=0 and p=0 in above equation.
∴ T(m) = θ( m^(log_4/31)log⁽⁰⁺¹⁾m)

Now applying, log_4/31 = 0
∴ T(m) = θ( m⁰log¹m)
∴ T(m) = θ(log m)

So, Option (1) is correct answer.

Algorithms: Masters theorem
T(n) = a T(n/b) + Θ(n^k log^p n) where a > = 1, b > 1, k > = 0 , and p is real number

Case 1: if a > b^k, Then T(n) =Θ(n^(log_ba))

Case 2: a = b^k
a)if p > -1, Then T(n) = Θ( n^(log_ba)log^(p+1)n)
b)if p = -1, Then T(n) = Θ( n^(log_ba)loglogn)
c) if p < -1, Then T(n) = Θ( n^(log_ba))

Case 3: a < b^k, a)if p > =0, then T(n) = Θ(n^k log^p n))
b) if p<0 then T(n) = Θ(n^k)

Previous	Next
UGC NET CS 2018 July - II Question 20	UGC NET CS 2018 July - II Question 22