# Need the type of time complexity and its formula

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?
• 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 Jul 25 at 2:25
• Cross-posted on MathOverflow Jul 25 at 2:30
• 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}$, ... Jul 25 at 14:25

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.

• Thank you. Can we consider it as a pesudo polynomial time? Jul 25 at 12:42
• 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.
– Jut
Jul 25 at 12:48
• @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. Jul 25 at 14:44

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).$$

• Thank you. Can we consider it as a pesudo polynomial time? Jul 25 at 12:42
• 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. Jul 25 at 12:50