Complexity of recursion with floor division $f(N) = F(N) - \sum_{m=2}^N f \left(\left\lfloor\frac N m \right\rfloor\right)$

Question

Often in computational number theory, to compute $f(N)$, there are identities like

$$F(N) = \sum_{m=1}^N f \left(\left\lfloor\frac N m \right\rfloor\right) $$

where $F(N)$ is easy to compute, i.e. $O(1)$ time, so can be rewritten (see Efficient computation of $\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor$)

$$f(N) = F(N) - \sum_{m=2}^N f \left(\left\lfloor\frac N m \right\rfloor\right)$$

There are more elaborate ways to rewrite, including using $\sqrt{N}$ as a cutoff for switching from computing $f(\lfloor N/m\rfloor)$ to iterating through $f(m)$, and pulling out even $m$ terms as $F(\lfloor N/2\rfloor)$.

What is the time complexity of computing $f(N)$ if all values are memoized?

For example, $f(100)$ depends on all the values of $\lfloor N/m \rfloor$, in this case $f(50), f(33), f(25), f(20), f(16), \dots, 50 \times f(1) $.

How can I analyze this? It's obvious we never need to call at least half of the $N$ values, $f(m)$ for $N/2 < m \le N$. The recursive calls depend on how many distinct $f(\lfloor N/m\rfloor)$ there are and their magnitudes. $a(N) = |\{\lfloor N/m \rfloor, 2 \le m \le N\}|$ doesn't seem to be on OEIS, unless I computed incorrectly.

[len(set([N//m for m in range(2, N+1)])) for N in range(2, 100)]

Answer 1

Here's my attempt at a version of this which seems to be easy to analyze. If we reverse the order of the summation (largest values of $m$ first), then I claim that we never need to recurse beyond depth 1. When we're expanding the summands of $f(\lfloor N/m\rfloor)$, those look like $f(\lfloor\lfloor N/m\rfloor / b \rfloor)$ for some $b>1$, but this is exactly equal to $\lfloor N/(mb)\rfloor$ which we have already calculated in an earlier step since $mb>m$.

We know (see comments on OP) that there are roughly $2\sqrt{N}$ distinct values of $m$, so it is helpful to group them into two types:

• when $m > \sqrt{N}$ then $\lfloor N/m\rfloor < \sqrt{N}$, so for each of the integer values from $r=1$ to $r\approx\sqrt{N}$ we can, in constant time, count how many distinct $m$ have $\lfloor N/m\rfloor = r$, and multiply it by the value of $f(r)$.
• when $1 < m \le \sqrt{N}$ we go back to iterating over $m$ (in descending order), and the logic above means there is no deeper recursion so we just need to sum the $2\sqrt{N/m}$ memoized terms to expand $f(\lfloor N/m\rfloor)$.

So the total number of evaluations-and-memoizations of $f$ needed looks like $\sqrt{N}$ for the first type, plus $\sum_{m=2}^\sqrt{N} 2\sqrt{N/m}$ for the second type, which should be approximated by the corresponding integral which evaluates to (I think) $4 N^{3/4}$, nicely sublinear. And the memory footprint looks to be $O(\sqrt{N})$ as well.