UGC NET CSE | July 2018 | Part 2 | Question: 21

Question

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

• A. $\Theta (\lg \: m)$
• B. $\Theta (m)$
• C. $\Theta (m\lg  m)$
• D. $\Theta (\lg\lg  m)$

Comments

it should be O(log m).

---

ANY BASE CONDITION

---

$\Theta$ (log m)

a=1, b=4/3

Apply case 2 of Master's Theorem

---

Please provide answer with explanation

Answer 1

Use master's theorem.

a=1,b=4/3 ,k=0 and a=b^k.

T(n)=θ(log n)

Answer 2

for T(m) = aT(m/b) + m^klog^pm

a = 1 (satisfies,  required a >=1)

b=4/3 (satisfies, required b>1)

k = 0 (satisfies, k>=0)

p=0 (satisfies, required p can be any real number)

we can Apply master's Theorem

now comparing a and b^k  ,we will get a = b^k

so, go for case when  a = b^k  and p > -1

we get T(m)= ⊖(m^log_balog ^p+1m) = ⊝(m^log_4/31log m) = ⊝ (log m)

Comments

Plz tell me how b=4/3

Answer 3

 in this problem use master theorm:

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

   compare both equation   a = 1;  b = 4/3

     m^(log _b a)  =  m ^0  = 1

      whenever       m^(log _b a)  and f(m) is equal than  answer is  f(m)* logm

 hence correct answer  1* log(m) = log(m)

Comments

Thanks for providing solution with explanation

Answer 4

Option A

Using Master's Thm:
$T(m) = aT(\frac{m}{b}) + \Theta (n^{k} log^pn)$ 

here , a =1, b= 4/3, k=0, p=0
hence  a = $b^k$ and p>-1
then, $T(m) = \Theta (n^{\log a}\log^{p+1}m )$
= $\Theta (n^0 \log ^1m )$ =
$\Theta(\log m)$