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?

Answer: D. (ii) and (iv) — 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. A.

    (i) and (iii)

  2. B.

    (i) and (iv)

  3. C.

    (ii) and (iii)

  4. D.

    (ii) and (iv)

Attempted by 119 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.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…