Solution: 2019 Fall Midterm - 14

Consider the following recursive algorithm $\ElisaDrinksCider$, which takes as input an integer $n \geq 1$, which is a power of 2:

$\ElisaDrinksCider(n):$
$\quad \mathbf{if}\ n = 1\ \mathbf{then}$
$\quad \quad \text{then order Fibonachos}$
$\quad \mathbf{else}$
$\quad \quad \ElisaDrinksCider\left(n \middle/ 2 \right)$
$\quad \quad \mathrm{drink}\ n\ \text{bottles of cider}$
$\quad \quad \ElisaDrinksCider\left(n \middle/ 2 \right)$

For $n$ a power of 2, let $C(n)$ be the total number of bottles of cider that you drink when running algorithm $\ElisaDrinksCider(n)$. Which of the following is true for any $n \geq 1$ that is a power of 2?
(n.b., $\log$ denotes the base-2 logarithm)