GATE 2022 CS – Question 51
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?
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.$
- **(A) $f(2^n-1)=2^n-1$:** $f(1)=1,\ f(3)=3,\ f(7)=7$. By induction $f(2^{n}-1)=2f(2^{n-1}-1)+1=2^n-1$. True.
- **(B) $f(2^n)=1$:** $f(2^n)=2f(2^{n-1})-1=2(1)-1=1$. True.
- **(C) $f(5\cdot2^n)=2^{n+1}+1$:** $f(5)=3,\ f(10)=5,\ f(20)=9,\ f(40)=17$, i.e. $2^1+1,\ 2^2+1,\ 2^3+1,\ 2^4+1$. True.
- **(D) $f(2^n+1)=2^n+1$:** $f(5)=3\ne5$. False.
Answer: A, B, C.
More Asymptotic Analysis and Time/Space Complexity questions
- GATE 2021 CS (CS1) Q13
- GATE 2021 CS (CS1) Q40
- GATE 2020 CS Q12
- GATE 2019 CS Q47
- GATE 2015 CS (CS1) Q60
- GATE 2015 CS (CS1) Q64
All Asymptotic Analysis and Time/Space Complexity questions →