Question: 2015 Fall Midterm - 14

Author: Michiel Smid

Consider the following recursive algorithm $\JustinBieber$, which takes as input an integer $n \geq 1$, which is a power of 2: (see document for missing code) For $n$ a power of 2, let $B(n)$ be the number of times you print "I don't like Justin Bieber" when running algorithm $\JustinBieber(n)$. Which of the following is true?
(n.b., $\log$ denotes the base-2 logarithm)

(a)

$B(n) = \log n - 1\ \text{for all}\ n \geq 1.$

(b)

$B(n) = n - 2\ \text{for all}\ n \geq 2.$

(c)

$B(n) = \log n - 1\ \text{for all}\ n \geq 2.$

(d)

$B(n) = \log n\ \text{for all}\ n \geq 2.$