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!
No comments:
Post a Comment