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&lt;\prod_{i=1}^nk_i\leqslant K\in\Bbb N,\ k_i \in \Bbb N^{+}\setminus\{1\}&amp;\  \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.
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))$.