The GATE Grind

GATE 2022 CS – Question 51

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple select

Consider the following recurrence:
$f(1)=1$;
$f(2n)=2f(n)-1$, for $n\ge1$;
$f(2n+1)=2f(n)+1$, for $n\ge1$.
Then, which of the following statements is/are TRUE?

  1. $f(2^n-1)=2^n-1$
  2. $f(2^n)=1$
  3. $f(5\cdot2^n)=2^{n+1}+1$
  4. $f(2^n+1)=2^n+1$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $f(2^n-1)=2^n-1$; (B) $f(2^n)=1$; (C) $f(5\cdot2^n)=2^{n+1}+1$

Explanation

Computing gives f(2)=1, f(3)=3, f(4)=1, f(5)=3, f(7)=7, f(8)=1 and f(10)=5, f(20)=9. Values are consistent with A, B and C by induction. D fails since f(5)=3 ≠ 5.