So today while reading wiki for graph algorithms, I came across this term **n****!! **called double factorial. Naturally, I was petrified. A factorial time complexity is scary enough, how horrible would **double**** **factorial be? In my mind I was assuming all sorts of irrational expressions such as:

n!! = (n-1)!!(n-1)!!

= ((n-2)!! (n-2)!!)( (n-2)!! (n-2)!!)

= … [*You** **get** *i*t**,** **right**?**]*

*But** **as** **it** *turns *out**, *double factorials are not so bad after all. Actually:

n!! = n*(n-2)* (n-4)*(n-6)*…

With terminal conditions 0!! = 1!! = 1.

So, a double factorial is actually has similar complexity to sqrt(n!).

Great!

** **

Advertisements