Solution: 2015 Fall Midterm - 14

Author: Michiel Smid

Question

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) = \log n\ \text{for all}\ n \geq 2.$

(c)

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

(d)

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

Solution

Let’s run the algorithem for n=1, n=2, n=4, and n=8 to see how many times it says \enquote{I don’t like Justin Bieber}.

JustinBieber$(1)$ = 0

JustinBieber$(2)$ = 0

JustinBieber$(4)$ = 1

JustinBieber$(8)$ = 2

JustinBieber$(16)$ = 3

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

Thus, the correct answer is $B(n) = \text{log } n - 1 \text{ for all } n \geq 2. $