1
$\begingroup$

If the complexity of my problem is $O(f_n(n))$ begins at $n =4$ and increases in this sequence:

At

$n = 4$ the number of operations = $(n - 2)$,

$n = 5$ the number of operations = $((n - 2) (n-2)(n-3)/2)$

$n = 6$ the number of operations = $((n - 2) (n-2)(n-3) (n-3)(n-4)/4))$

$n = 7$ the number of operations = $((n-2) (n-2)(n-3) (n-3)(n-4)(n-4)(n-5)/8)$

$n = 8$ the number of operations = $((n-2) (n-2)(n-3) (n-3)(n-4)(n-4)(n-5)(n-5)(n-6)/16 )$ … etc.

  1. How to formulate the $f_n(n)$ for all $n$?
  2. What is the type of its time complexity?
$\endgroup$
3
  • 2
    $\begingroup$ Welcome to CS SE! You'll get a lot more help by providing context. Where did you find this problem? Also, what have you tried? Where did you get stuck? You'll receive a lot more help this way $\endgroup$
    – devam_04
    Jul 25 at 2:25
  • $\begingroup$ Cross-posted on MathOverflow $\endgroup$ Jul 25 at 2:30
  • $\begingroup$ It's probably much easier to figure out if you drop the $n-X$ and write the actual numbers (and group the terms): 4: $\frac{2}{1}$, 5: $\frac{\left(3\right)\cdot\left(2\cdot3\right)}{2}$, 6: $\frac{\left(2\cdot3\cdot4\right)\cdot\left(3\cdot4\right)}{4}$, ... $\endgroup$ Jul 25 at 14:25
0
$\begingroup$

1.)

If we look at $n=8$ then we see: $$\frac{1}{2^4}\times\left((n-6)(n-5)(n-4)(n-3)(n-2)\right)\times \left((n-5)(n-4)(n-3)(n-2)\right)$$ $$=\frac{((n-2)!)^2}{2^5}.$$

Therefore we can formulate $f_n(n)$ as follow:

$$f_n(n)=\frac{n-(n-2)}{2^{n-4}}\times \prod_{i=3}^{n-2}i^2$$ $$=\frac{n-(n-2)}{2^{n-4}}\times \prod_{i=3}^{n-2}i\times \prod_{i=3}^{n-2}i$$ $$=\frac{2}{2^{n-4}}\times \frac{(n-2)!}{2}\times\frac{(n-2)!}{2}$$ $$=\frac{\left((n-2)!\right)^2}{2^{n-3}}.$$ So we find a closed formula for $f_n(n)$.

2.)

Let $T(n)$ be the time complexity of computing $f_n(n)$: $$T(n)=\Theta\left(\frac{\left((n-2)!\right)^2}{2^{n-3}}\right).$$ That you can estimate it by sterling's approximation.

$\endgroup$
3
  • $\begingroup$ Thank you. Can we consider it as a pesudo polynomial time? $\endgroup$
    – SAbeA
    Jul 25 at 12:42
  • $\begingroup$ No, obviously the complexity is super-exponential. Note that, when you use the term, pseudo polynomial, it's means that, the complexity depend on the value, not only the size of input. But if you look at $T(n)$, you can see that the running time only depend on $n$ not any other variables. $\endgroup$
    – Jut
    Jul 25 at 12:48
  • $\begingroup$ @SAbeA Factorials are superexponential (i.e. grow faster than exponential functions with a constant base $c^n$). So we know $\lim\frac{(n-2)!}{2^{n-3}} > 1$, thus $\frac{\left((n-2)!\right)^2}{2^{n-3}} = (n-2)!\frac{(n-2)!}{2^{n-3}}$ is also superexponential. $\endgroup$ Jul 25 at 14:44
2
$\begingroup$

It seems that: $$ f(n) = \left( 2\prod_{i=3}^{n-2} i^2 \right) \cdot \frac{1}{2^{n-4}} = \frac{1}{2^{n-5}} \cdot \frac{1}{2^2} \cdot\prod_{i=1}^{n-2}i^2 = \frac{1}{2^{n-3}} \cdot \left( \prod_{i=1}^{n-2}i \right)^2 = 2^{3-n} ((n-2)!)^2. $$

This time complexity is superexponential. Indeed, using Stirling's approximation: $$ 2^{3-n} ((n-2)!)^2 \sim 2^{3-n} \cdot 2\pi n \left( \frac{n-2}{e} \right)^{2(n-2)} = \Theta\left(\left(\frac{n}{\sqrt{2} \; e}\right)^{2(n-2)}\right). $$

$\endgroup$
2
  • $\begingroup$ Thank you. Can we consider it as a pesudo polynomial time? $\endgroup$
    – SAbeA
    Jul 25 at 12:42
  • $\begingroup$ A pseudopolynomial running time is a time that is polynomial in the maximum value $t$*represented* by the input. You gave us no information on what the input represents. Anyway, using standard representation, an instance size of $n$ can represent integers up to $2^n$. Let's be optimistic and pick $t=2^n$. Then $f(n) = \Omega( \frac{(\log t)^{\log t}}{\text{poly}\, t} ) = \Omega(\frac{2^{\log t \cdot \log \log t}}{\text{poly}\, t}) = \Omega(\frac{t^{\log \log t}}{\text{poly}\, t})$, so $f(n)$ is not polynomial in $t$ either. $\endgroup$
    – Steven
    Jul 25 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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