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

Compute small values from $f(1)=1,\ f(2n)=2f(n)-1,\ f(2n+1)=2f(n)+1$:
$f(2)=1,\ f(3)=3,\ f(4)=1,\ f(5)=3,\ f(6)=5,\ f(7)=7,\ f(8)=1,\ f(10)=2f(5)-1=5,\ f(20)=9,\ f(40)=17.$

Answer: A, B, C.

More Asymptotic Analysis and Time/Space Complexity questions

All Asymptotic Analysis and Time/Space Complexity questions →