List of practice Questions

Consider the following recurrence:
\[ f(1) = 1; \] \[ f(2n) = 2f(n) - 1, \text{ for } n \geq 1; \] \[ f(2n+1) = 2f(n) + 1, \text{ for } n \geq 1. \] Then, which of the following statements is/are TRUE?

For constants \(a \geq 1\) and \(b > 1\), consider the following recurrence defined on the non-negative integers:
\[ T(n) = a \cdot T\!\left(\frac{n}{b}\right) + f(n) \] Which one of the following options is correct about the recurrence \(T(n)\)?