O(1) solution for number of times to apply iterated function

Question

Is there an O(1) solution for finding the number of times to apply an simple iterated function to satisfy an inequality?

For example, if the function is

$$f(n) = 0.5n - 10; n > 100$$ and we want to solve $$\min (i \ge 0: f^i(n)\le 100)$$

Is there an $O(1)$ solution for this?

Answer 1

I don't think there's a good general theory that you can throw any function at and get good results.

In this case, however, the trick is to change the variable such that the function becomes a simple multiplication. We can do that by setting $m=n+a$, so our original iteration $$ n \mapsto 1.2 n - 10 $$ becomes $$ m \mapsto 1.2 (m-a) - 10 + a $$ which rearranges to $$ m \mapsto 1.2m + (a - 10 - 1.2a) $$ Here we want to constant term to be 0; solving $a-10-1.2a=0$ yields $a=-50$, so with $m=n-50$ we have $$ m \mapsto 1.2 m $$

Then $n = 100 $ corresponds to $m = 50 $, so the $i$ for which $1.2^i m = 50$ must be $\log_{1.2}(50/m)$.

However, it does not really make sense to ask for the first $i$ for which $f^i(n)\le 100$, because the iteration causes the point to diverge away from $n=50$ -- so unless the initial $n$ is already less than $100$, no amount of iterating the function will ever make it become less than $100$.

Answer 2

Task:

Given $n > 100$ we have the set $$ A_n = \{ i\in \mathbb{N} \mid f^i(n) \le 100 \} $$ Wanted is the minimum of $A_n$. We write
$$ F(n) = \min A_n $$ and assign it the value $\bot$ if the minimum does not exist.

Calculating $f^i$ from $f$:

If we have $$ f(n) = c\, n - d \quad (c, d \ge 0) $$ then $$ f^2(n) = c(c \, n - d) -d = c^2 \, n - d (c + 1) = c' \, n - d' \quad (c', d' \ge 0) $$ and thus $$ f^i(n) = c^{(i)} n - d^{(i)} \quad (c^{(i)}, d^{(i)} \ge 0) $$ with $$ c^{(i)} = c^i \\ d^{(1)} = d \\ d^{(2)} = c d + d = (c+1) d \\ d^{(3)} = c((c+1) d) + d = (c(c+1) + 1) d = (c^2 + c + 1) d \\ d^{(i+1)} = c \, d^{(i)} + d \quad (i \ge 1) \\ d^{(i+1)} = d \sum_{k=0}^i c^i = \begin{cases} d (c^{i+1}-c)/(c-1) & \text{for } c \ne 1, i \ge 1 \\ d \, (i + 1) & \text{for } c = 1, i \ge 1 \end{cases} $$ which leads to $$ f^i(n) = \begin{cases} c \, n - d & \text{for } c \ne 1, i = 1 \\ c^i \, n - d (c^i-c)/(c-1) & \text{for } c \ne 1, i \ge 2 \\ n - d \, i & \text{for } c = 1 \end{cases} $$

Solution:

With the help of the above it just needs a couple of case distinctions depending on $n, c, d$ to either come up with a suitable $i$ or determining that no such $i$ exists. This is a $O(1)$ algorithm.

Here are some examples:

For $c = 1$ this means $$ f^i(n) = n - d\, i \le 100 \Rightarrow \\ n - 100 \le d \, i \Rightarrow \\ F(n) = \begin{cases} \bot & \text{for } d = 0 \\ \lceil (n - 100)/d \rceil & \text{for } d \ne 0 \end{cases} $$ For $c \ne 1$ and $i\ge 2$ we have $$ c^i \, n - d (c^i-c)/(c-1) \le 100 \Rightarrow \\ (n - d/(c-1)) c^i \le 100 - dc/(c-1) $$ This requires a case distinction for $n - d/(c-1)$. If it is negative, thus $n < d/(c-1)$ and $c >1$ we have $$ i \ge \frac{\ln\left(\frac{100-dc/(c-1)}{n - d/(c-1)}\right)}{\ln(c)} \\ F(n) = \left\lceil \frac{\ln\left(\frac{100-dc/(c-1)}{n - d/(c-1)}\right)}{\ln(c)} \right\rceil $$ The other cases are handled in a similar way.