recategorized by
2,129 views
0 votes
0 votes

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

  1. $\Theta (\lg \: m)$
  2. $\Theta (m)$
  3. $\Theta (m\lg  m)$
  4. $\Theta (\lg\lg  m)$
recategorized by

4 Answers

3 votes
3 votes

for T(m) = aT(m/b) + mklogpm

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 ,we will get a = bk

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

we get T(m)= ⊖(mlogbalog p+1m) = ⊝(mlog4/31log m) = ⊝ (log m)

2 votes
2 votes

 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)

1 votes
1 votes

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)$


 

Related questions

0 votes
0 votes
1 answer
1
Pooja Khatri asked Jul 13, 2018
2,368 views
Match the following with respect to algorithm paradigms :$\begin{array}{clcl} & \textbf{List-I} & {} & \textbf{List-II} \\ \text{(a)} & \text{The 8-Queen's problem} & \t...
0 votes
0 votes
2 answers
2
Pooja Khatri asked Jul 13, 2018
1,981 views
Consider a Boolean function of 'n' variables. The order of an algorithm that determines whether the Boolean function produces a output 1 isLogarithmicLinearQuadraticExpon...
1 votes
1 votes
2 answers
3
Pooja Khatri asked Jul 13, 2018
2,655 views
The definitions in an XML document are said to be ______ when the tagging system ans definitions in the DTD are all in compliancewell-formedreasonablevalidlogical