in Algorithms
3,746 views
2 votes
2 votes
1) $T(n)=T(n/2)+2^n$

2) $T(n)=2T(n/2)+n / \log n$

3) $T(n)=16T(n/4)+n!$

4) $T(n)= \sqrt 2T ( n/2 ) + \log n$
in Algorithms
3.7k views

2 Comments

1. T(n) = ⊖(2n)

2. ??

3. T(n) = ⊖(n!)

4. T(n) = ⊖(√n)

How to solve second part??

1
1
How other parts be solved ??
1
1

1 Answer

2 votes
2 votes
Best answer

1,3,4 can be solved by Master's Theorem, not sure about 2

1.

$f(n)= 2^n , a=1, b=2$
$f(n)=  \Omega\left(n^{\log_b a + \epsilon }\right)$. Any $\epsilon \in \mathbb{N}$ would do as exponential function grows faster than polynomial.Now, for Master theorem case 3 we need to see regularity condition also, which is 

$$af\left(\frac{n}{b}\right) \leq c f(n), c < 1$$

$\implies 2^{\frac{n}{2}} \leq c 2^n$

$c = 0.5$ works here and so we can apply Master theorem Case 3

   $$T(n) = \Theta(f(n)) = \Theta\left( 2^n \right)$$

3.     

$f(n) = n! , a = 16, b = 4$
$f(n) =  \Omega\left(n^{\log_b a + \epsilon }\right)$. Any $\epsilon$ would do as factorial grows at a faster rate than polynomial. So, we have Case 3 of Master theorem which also requires the regularity check.

$$af\left(\frac{n}{b}\right) \leq c f(n), c < 1$$

$\implies 16 . {\frac{n}{4}} ! \leq c n!$

is surely true for $c = \frac{1}{16}$. So, we can apply Case 3 of Master theorem and so, $$T(n) = \Theta(f(n)) = \Theta( n! )$$


4.      

$f(n) = \log n , a =  √2, b = 2$
$f(n) =  O\left(n^{\log_b a - \epsilon}\right )$   take $\epsilon  = 0.1$
Master theorem Case 1 and hence, $$T(n) = \Theta\left(n^{\log_2 \sqrt2} \right)= \Theta( \sqrt n )$$

For 2 we can't apply Master theorem- why because $n^{\log_b a} = n^{\log_2 2} = n$. Now $n/ \lg n = O(n)$ is true but we can't write $n/\lg n = O\left(n^{1 - \epsilon}\right)$ for any positive epsilon. Thus we can't apply master theorem. Solution can be obtained using Extended Master theorem or solving recurrence directly. You can see the below link. 

https://gateoverflow.in/10619/recurrence

selected by

3 Comments

@Arjun sir

af(n/b)<=cf(n) is it correct?

or it should be af(n/b)<cf(n)
0
0
it is $\leq$,
0
0
In case 3, can someone please explain how

$16.(n/4)! <= cn!$

is satisfied by c = 1/16?
0
0

Related questions