Is O((n-1)(n-3)(n-5)...(n-n+1)) considered O(n!) running time?

Question

I found the worst-case running time of my algorithm to be O((n-1)(n-3)(n-5)...(n-n+1)). Is this considered O(n!) or does it simplify to a lower running time?

Answer 1

There are some steps we can use to come up with the answer for n!! in terms of n! and n. Firstly, in n!!, we have half as many terms as we would in n!. So we can imagine taking n! and 'dividing out' (n/2)!. So this is 1*2*3*4...n / (1*2*3*4...n/2) in the first step.

However, this isn't quite right, since we want to remove all the even numbers, not all the numbers less than n/2! What's nice, however, is that now we can take every term in the denominator, individually, and multiply it by 2 to get 2*4*6*8...(n-2)*n. If we then 'factor out' all the *2s that we just used, we'd have exactly (n/2) of them (since there were n/2 elements in this sequence, and we doubled all of them). Thus, n!! = n! / ((n/2)! * 2^(n/2)). So, O(1*3*5*7...*(n-2)*n) = O(n!/((n/2)!2^(n/2)) which is better than n! (since we're at least dividing an exponential and a smaller factorial!). Hope this makes sense

Answer 2

Firsty, when you talk about running time you should use T(n) = (n - 1)(n - 3)..(n - n + 1). Secondly, it is not considered O(n!), you can provide better evalution for worst-case time complexity:

• 1 * 2 * 3 * ... * n = n!
• 2 * 4 * 8 * ... * n = 2^(n/2) * (n/2)!

divide equations

1 * 3 * 5 * ... * n = n! / (2^(n/2) * (n/2)!)

So, your final worst-case complexity is O(n! / (2^(n/2) * (n/2)!)) and it's pretty obvious why this evaluations is different from O(n!).