The function f is defined as follows: int f (int n) { if (n <= 1) return 1;…
2007
The function f is defined as follows:
int f (int n) {
if (n <= 1) return 1;
else if (n % 2 == 0) return f(n/2);
else return f(3n - 1);
}
Assuming that arbitrarily large integers can be passed as a parameter to the function, consider the following statements.
1. The function f terminates for finitely many different values of n ≥ 1.
ii. The function f terminates for infinitely many different values of n ≥ 1.
iii. The function f does not terminate for finitely many different values of n ≥ 1.
iv. The function f does not terminate for infinitely many different values of n ≥ 1.
Which one of the following options is true of the above?
- A.
(i) and (iii)
- B.
(i) and (iv)
- C.
(ii) and (iii)
- D.
(ii) and (iv)
Attempted by 93 students.
Show answer & explanation
Correct answer: D
Answer: (ii) and (iv).
Reason:
There are infinitely many inputs for which f terminates. If n is a power of two (n = 2^k with k ≥ 0), repeated halving reaches 1, so f(2^k) returns 1. Thus statement (ii) is true.
There are infinitely many inputs for which f does not terminate. The number 5 enters a nontrivial cycle: 5 → 14 → 7 → 20 → 10 → 5, so f never reaches the base case for 5. Any number of the form 2^k * 5 (k ≥ 0) is even-power-multiples of 5 and will be reduced by dividing out factors of two until it reaches 5, hence all these infinitely many inputs also do not terminate. Therefore statement (iv) is true.
Because both infinitely many terminating and infinitely many non-terminating inputs exist, the claims that only finitely many terminate or only finitely many do not terminate are false. Thus statements (i) and (iii) are false.