# Time complexity of a recursive enumeration in the problem of finding n-tuples of naturals greater than 1 with bounded product

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: $$$$f(K, n) = \sum_{k=2}^{\lfloor \frac{K}{2^{n-1}}\rfloor} \bigg(1 + f(\lfloor \frac{K}{k} \rfloor, n - 1)\bigg)$$$$ $$$$f(K, 0) = 0$$$$

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.

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: $$$$T(K, n) = \sum_{k=1}^{K} T(\lfloor \frac{K}{k} \rfloor, n - 1)$$$$ $$$$T(K, 0) = 1$$$$ where $$T(K, 0)$$ is the number of elementary operations in the basic case.
For any bound $$x$$, we know that: $$$$T(x, 1) = \sum_{k=1}^{x} T(x, 0) = x$$$$
Moreover, for $$T(x, 2)$$ we have: $$$$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}$$$$ We can see that this is in fact finite partial sum of harmonic series: $$$$T(x, 2) = x \sum_{k=1}^{x} \frac{1}{k} = x H_x$$$$ 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: $$$$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$$$$ Now we can bound $$T(x, 3)$$: $$$$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$$$$
By induction, we get that $$T(K, n) = K H_K^{n-1}$$. Harmonic number can be approximated with integral: $$$$H_K = \int_{1}^{K} \frac{1}{t} dt = \ln K$$$$
Therefore, an upper bound on complexity is given with $$O(K \log^{n-1} (K))$$.