This is an exercise of a technique called memorization in recursion.

Let us first consider the complexity of a naive recursion.

(To be written)

Next, let us consider the complexity if we use a memorization.

Consider distinct values of arguments of \(f\). Such values is limited to those that can be represented by \(\displaystyle\Big \lfloor \frac{N}{2^x3^y}\Big\rfloor\) with non-negative integers \(x\) and \(y\).

As a rough estimate, \(x+y\) can be \(\log_2{N}\) or fewer, so the number of distinct arguments is \(\mathrm{O}(\log^ 2N)\). Thus, the memorization enabled us to solve this problem in a total of \(\mathrm{O}(\log ^2N)\) time.