Designing A Constant-Time Algorithm For A Function

Question

This question just went over my head:

A function G(m) is defined as below:

a) If m <= 100 then G(m) = G(G(m + 11))

b) If m > 100 then G(m) = m – 10

According to above question, how do I design a constant-time algorithm that calculates G(m)?

Answer 1

The (b) part can obviously be computed in constant time, assuming m fits in an integer variable.

The tricky part the problem is asking to prove is that the (a) part is constant. Then the O(1) time follows. That can be done using mathematical induction or in some other way.

The inductive proof follows.

First observe that G(101) is equal to 101 - 10 = 91 by definition.

For 90 <= n <= 100 it holds that G(n) = G(G(n + 11)), where n + 11 > 100. Therefore G(n) it is equal to G(n + 11 - 10) = G(n+1), which is 91.

From this, the the ten equations G(91 - 1) = 91, G(91 - (1 - 1)) = 91, ..., G(91 - (1 - 10)) = 91 are all true. This is the base for the general induction.

The inductive step: assume that G(91 - i) = 91, G(91 - (i - 1)) = 91, ..., G(91 - (i - 10)) = 91 is true for all numbers i from 1 up to a certain bound.

Then G(91 - (i + 1)) = G(G(91 - i - 1 + 11)) = G(G(91 - (i - 10))). From the base step, we know that G(91 - (i - 10)) = 91. Plugging this in the equation above, we get G(91), which is also already known to be 91. From this it follows that the assumption is true for i+1 as well.

Consequently, G(91 - n) is equal to 91 for all n >= 1. The induction is proven.

An example of the constant-time algorithm for computing G in Python:

def G(m):
   if m > 100:
      return m - 10
   else:
      return 91