in Algorithms
785 views
3 votes
3 votes
Can we apply master theorem  on following RR

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

if yes then how
in Algorithms
785 views

4 Answers

2 votes
2 votes
Yes, Master theorem can be applied

a = 16

b = 4

k = n    which is large obviously

According to master theorem 3rd property

t(n) = O(n^k)

so t(n) = O(n^n)
1 vote
1 vote

Yes, it can be applied because here a>=1, b>1,

F(n) =n!

According to master theorem 3rd property which says that if

f(n) =Ω(nlogb a +ϵ) then T(n) = (f(n))

here nlogba =n^2

f(n)= n! = n (n-1) (n-2)! = n^2 (n-2)! - n(n-2)!

=>f(n)=Ω(n^2 +ε)

therefore T(n)=∅(n^n)

4 Comments

can we solve it by using extened master theorem???
0
0

@Sarvottam. I will try to explain Stirling's approxition.

Consider, the approximation $log(n!) = \Theta (log(n^n))$

We want to show that this is true for very large values of 'n'. Lets have n = $2^{100}$ = ${10}^{30}$

Now, log(n!) = log(n) + log(n-1) + ... + log(2) + log(1)

and, $log(n^n)$ = log(n) + log(n) + log(n)...'n' times

Note: We are adding the log terms

So, log(n) = 100 which means that  $log(n^n)$ = 100*${10}^{30}$ = ${10}^{32}$

So, even for huge 'n', we are getting log(n) = 100.

Value of log(n!) is much more comparable to $log(n^n)$ since we have added the log terms.

But, we have considered the base as 2. If the base is 10 or something greater, then the difference between
log(n!) and $log(n^n)$ becomes much less. Hence, the Stirling's approximation.

But, $n^n$ is a huge  figure as compared to n! and its a bad approximation because here, we are multiplying the terms(Consider multiplying the highest  order  terms manually and check the difference for both).

So, Never appoximate $n!$ by $n^n$ .

1
1

@Sushant I agree

So here f(n) is O(n^n) and not Ø(n^n)

1
1
0 votes
0 votes
Here we have two function named F(n) and G(n).

F(n)=n^2,G(n)=n!.

Now clearly, there may be asymptotic comparison  b/w F(n) and G(n).Hence master theorem can be applied.
0 votes
0 votes
Answer is ϕ( n! ) by master theorem.