0

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

I know it can be solved using Master theorem, but I don't know how to handle f(n) = n!

Ujjawal
  • 1
  • 1
  • 2
  • Did you checked the time complexity calculating procedure described [here](http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm?answertab=active#tab-top)? – masud_moni Nov 04 '16 at 05:40
  • @masud_moni yes. I was not able to find anything useful. – Ujjawal Nov 04 '16 at 05:43
  • what have you tried? have you tried unrolling it a few times to look at the pattern? anyway this is case 3 of Master Theorem – softwarenewbie7331 Nov 04 '16 at 05:44
  • @softwarenewbie7331 Here, a = 16, b = 4, f(n) = n!. What should I take the value of c as? – Ujjawal Nov 04 '16 at 05:49

1 Answers1

2

This is case three of Master Theorem.

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

Here f(n) = n!.

a = 16 and b = 4, so logb a = log4 16 = 2.

Master Theorem states that the complexity T(n) = Θ(f(n)) if c > logb a where f(n) ∈ Ω(nc) . Since f(n) = n! > nc for some value of n > n0 the statement f(n) ∈ Ω (nc) is true. Thus the statement c > logb a =2 is also true. Hence by the third case of Master Thoerem the complexity T(n) = Θ(f(n)) = Θ(n!).

Deepu
  • 7,592
  • 4
  • 25
  • 47