Double Factorial

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 it, 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s