3
$\begingroup$

Suppose an algorithm is $O(n!)$, but we need to run it $n$ times, so the total complexity is

$nO(n!) = O(n \cdot n!) = O((n+1)! - n!) = O((n+1)!)$

Strictly, there is no constant factor that would make $n!$ greater than $(n+1)$, but it seems pointless to indicate that there is a constant shift.

Is it ok to write $O((n+c)!) ≈ O(n!)$ or even $O((n+c)!) = O(n!)$, when $c$ is constant?

$\endgroup$

1 Answer 1

3
$\begingroup$

No, $(n+1)!$ is not $O(n!)$. There is no constant factor $c_0$ so that $(n+1)!$ is at most $c_0 \times n!$.

You can say that $(n+1)!$ is in $O(n! \times \text{poly}(n))$. Here $\text{poly}(n)$ represents the class of functions that grow polynomially fast in $n$; so in other words, this statement says that there is a polynomial $p(n)$ so that $(n+1)!$ is in $O(n! \times p(n))$. Indeed, it is also true that $(n+c)!$ is in $O(n! \times \text{poly}(n))$. This may be enough for your purposes.

Sometimes people may define new notation for this kind of case. For instance, if we are dealing with functions that grow exponentially fast, and we don't care about a factor of $n$ (which grows much more slowly than any exponential function), we might define $f(n) = O^*(g(n))$ if $f(n)$ is in $O(g(n) \times \text{poly}(n))$. Then it is true that $(n+c)!$ is in $O^*(n!)$.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks! I think I'll just use O*. It seems to be common enough to not need explaining in my case. cs.stackexchange.com/questions/87432/… $\endgroup$
    – TrayMan
    Commented May 18, 2021 at 19:09
  • 2
    $\begingroup$ @TrayMan, I definitely recommend you define what you mean by it before using it. As mentioned in a comment there, its meaning can vary and it does not have a single standard accepted meaning. $\endgroup$
    – D.W.
    Commented May 18, 2021 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.