CODEWITHSUNDEEP
algorithmtime-complexity
user5716274
user5716274

Reputation:

Do we have a non factorial function which is Θ(n!)?

So i know that f(n)=n^n has a bigger growth compared to g(n)=n! and t(n)=2^n has a less growth

but i can't find any function that has the same order as n! and is not a factorial function

do we have such a function which is Θ(n!) and is not factorial? if we do have such functions then can you mention a few?

Upvotes: 1

Views: 346

Answers (3)

Alexandre Dupriez
Alexandre Dupriez

Reputation: 3036

Yes - one of the most famous asymptotic equivalent of n! is given by its Stirling's approximation, namely:

(1)  n! ~ sqrt(2.pi.n).(n/e)^n

Note the use of equivalence which is stronger than the Θ relationship. The former implies the latter:

(2)  f(n) ~ g(n) => f(n) = Θ(g(n))

With (1) and (2) you get:

n! = Θ(sqrt(2.pi.n).(n/e)^n)

Since you are asking for a Θ approximation rather than an equivalence, you can create as many functions as you want, for instance multiplying by 2 - sin(n) (which isn't particularly useful!):

n! = Θ((2 - sin(n)).sqrt(2.pi.n).(n/e)^n)

Upvotes: 4

meowgoesthedog
meowgoesthedog

Reputation: 15035

A simple example is computing all possible permutations of an array:

  • n choices for first element
  • n - 1 for 2nd
  • n - 2 for 3rd
  • and so on ...

In total there are n(n - 1)(n - 2)... = n! permutations (if elements are unique or tagged).

Upvotes: 1

DoomzDay
DoomzDay

Reputation: 39

Take a look at Double Factorial and try to compare them.

Upvotes: -1

Related Questions