How to optimize a recursive algorithm w.r.t. time and space requirements

Question

I'm quite new to the examination of algorithms and struggle a bit at the following exercise:

The following function F(x) has the real numbers as input:

 -FUNCTION F(x):REAL
            if x ≤ 2 
               then RETURN(1)
            else
               h := 0
               for i := 1 to 4 do
                   h := h + i ∗ F(x − 2)
                   RETURN(h)

Develop an alternative version of this function which is (asymptotically) as efficient with respect to time and space requirements as possible.

By playing with the above function I found out that it has the following form:

$F(x) = 1 \ \ \ \ \ \ (x ≤ 2)$

$F(x) = 10 \ \ \ \ \ \ (2 < x ≤ 4)$

$F(x) = 100 \ \ \ \ \ \ (4 < x ≤ 6)$

...............

This makes sense since we can easily see that we may replace the for-loop in the above algorithm by $10*F(x-2)$ giving us :

 -FUNCTION F(x):REAL
            if x ≤ 2 
               then RETURN(1)
            else
               RETURN(10*F(x-2))

Then I found the below algorithm G, which I "intuitively" believe to be a good option for this task:

  -FUNCTION G(x):REAL
            if x ≤ 2 
               then RETURN(1)
            else
               RETURN( 10^(⌈n/2⌉-1) )

My problem is that I don't know how to prove that G does "the same" as F. The main problem for me is that this algorithms are defined over the real numbers instead of the natural ones, therefore hindering a proof by induction.

I would gladly appreciate any kind of hints or help.

Thanks in advance.

Answer 1

We can use induction to prove claims about real numbers if we can "group" them into claims indexed by natural numbers.

In this case, one way to do that might be to prove, by induction, that the statement $$\text{If }2n < x \le 2n+2, \text{ then }F(x) = 10^n$$ is true for all $n$. Or, more practically, we could consider the statement that $$\text{If }2n < x \le 2n+2, \text{ then }F(x) = G(x)$$ skipping directly to the claim that your new function does the same thing as the old one.

In either case, the reason this works is that:

• For $n=0$, either statement tells us something about what $F(x)$ does when $x \le 2$, which is part of the non-recursive definition of $F(x)$. So we can verify the base case.
• When proving the statement for some value of $n$, we are evaluating $F(x)$ for $x \in (2n, 2n+2]$, which recursively calls $F(x-2)$. But $x-2 \in (2n-2, 2n]$, so it's a value that the statement for $n-1$ talks about. So we can apply the inductive hypothesis to $F(x-2)$.

Anyway, once we've gotten over this "philosophical" hurdle, writing the actual proof by induction probably won't be hard for you. (You've done the real work of figuring out $G(x)$, after all.)