1
$\begingroup$

I have to determine the time complexity of a recursive enumeration in the problem of finding n-tuples $(k_i, ..., k_n)$ of naturals greater than 1 with product less or equal to $K$. Problem can be formally expressed as: $$\begin{align}0<\prod_{i=1}^nk_i\leqslant K\in\Bbb N,\ k_i \in \Bbb N^{+}\setminus\{1\}&\ \forall i\in\{1,\ldots,n\},\end{align}$$

The number of steps required to enumerate all n-tuples of naturals greater than 1 is: \begin{equation} f(K, n) = \sum_{k=2}^{\lfloor \frac{K}{2^{n-1}}\rfloor} \bigg(1 + f(\lfloor \frac{K}{k} \rfloor, n - 1)\bigg) \end{equation} \begin{equation} f(K, 0) = 0 \end{equation}

I can provide trivial time complexity analysis. As every $k_i \leq \frac{K}{2^{n-1}}$ and there $n$ factors which can be in interval $[2, \frac{K}{2^{n-1}}]$, we have that the maximum number of steps is $(\frac{K}{2^{n-1}} - 1)^n$. Therefore, complexity in big-O notation should be $O\bigg(\frac{K^n}{2^{n^2-n}}\bigg)$. I do not know if this observation is of any relevance to the time-complexity analysis.

$\endgroup$
0
0
$\begingroup$

I thought about this problem a lot and I think that I devised a suitable solution. I focus here on asymptotic analysis with respect to $K$, and my aim is to provide tighter upper bound than one that I suggested in the question. Therefore, I now observe slightly different problem where $k_i \geq 1$. In that case the number of steps $T(K,n)$ required to enumerate all n-tuples of naturals greater or equal one 1 with product less than or equal to $K$ is: \begin{equation} T(K, n) = \sum_{k=1}^{K} T(\lfloor \frac{K}{k} \rfloor, n - 1) \end{equation} \begin{equation} T(K, 0) = 1 \end{equation} where $T(K, 0)$ is the number of elementary operations in the basic case.

For any bound $x$, we know that: \begin{equation} T(x, 1) = \sum_{k=1}^{x} T(x, 0) = x \end{equation}

Moreover, for $T(x, 2)$ we have: \begin{equation} T(x, 2) = T(\frac{x}{1}, 1) + T(\frac{x}{2}, 1) + T(\frac{x}{3}, 1)... + T(\frac{x}{x}, 1) = \frac{x}{1} + \frac{x}{2} + \frac{x}{3} ... + \frac{x}{x} \end{equation} We can see that this is in fact finite partial sum of harmonic series: \begin{equation} T(x, 2) = x \sum_{k=1}^{x} \frac{1}{k} = x H_x \end{equation} where $H_x = \sum_{k=1}^{x} \frac{1}{k}$ is the x-th harmonic number.

Now with $T(x, 2) = x H_x$, $T(x, 3)$ can be expressed as: \begin{equation} T(x, 3) = T(\frac{x}{1}, 2) + T(\frac{x}{2}, 2) + ... + T(\frac{x}{x}, 2) = x H_x + \frac{x}{2} H_{x/2} + ... + \frac{x}{x} H_1 \end{equation} Now we can bound $T(x, 3)$: \begin{equation} T(x, 3) = x H_x + \frac{x}{2} H_{x/2} + ... + \frac{x}{x} H_1 \leq x H_x (1 + \frac{1}{2} + ... + \frac{1}{x}) = x H_x^2 \end{equation}

By induction, we get that $T(K, n) = K H_K^{n-1}$. Harmonic number can be approximated with integral: \begin{equation} H_K = \int_{1}^{K} \frac{1}{t} dt = \ln K \end{equation}

Therefore, an upper bound on complexity is given with $O(K \log^{n-1} (K))$.

$\endgroup$

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.