Solution: 2016 Fall Midterm - 14

Author: Michiel Smid

Question

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

$\mathbf{Algorithm} \text{ ElisaDrinksCider}(n):$
$\quad \mathbf{if}\ n = 1\ \mathbf{then}$
$\quad \quad \text{order Fibonachos}$
$\quad \mathbf{else}$
$\quad \quad \ElisaDrinksCider(n / 2);$
$\quad \quad \text{drink n bottles of cider};$
$\quad \quad \ElisaDrinksCider(n / 2)$
$\quad \mathbf{endif}$

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)

(a)

$C(n) = n \log n - 1$

(b)

$C(n) = n \log n + 1$

(c)

$C(n) = 2n \log n$

(d)

$C(n) = n \log n$

Solution

We can calculate the first couple of values of $ C(n) $ to see if we can find a pattern.

$ C(1) = 0 $

$ C(2) = 2 $

$ C(n) = n log{ n } - 1 $
$ C(1) = 1 log{ 1 } - 1 = 0 $
$ C(2) = 2 log{ 2 } - 1 = 2 - 1 = 1 $
$ C(n) = n log{ n } n + 1 $
$ C(1) = 1 log{ 1 } 1 + 1 = 1 $
$ C(n) = n log{ n } n $
$ C(1) = 1 log{ 1 } 1 = 0 $
$ C(2) = 2 log{ 2 } 2 = 2 $
$ C(n) = 2n log{ n } n $
$ C(1) = 2(1) log{ 1 } 1 = 0 $
$ C(2) = 2(2) log{ 2 } 2 = 4 $

Thus, we know that $ C(n) = n log{ n } $ is the correct answer.