Solution: 2018 Winter Final - 10
Author: Michiel SmidQuestion
$\newcommand{\SundayEveningExam}{{\rm S {\scriptsize UNDAY} E {\scriptsize VENING} E {\scriptsize XAM}}}
\newcommand{\elsesp}{\phantom{\mathbf{else}\ }}$
Consider the recursive algorithm $\SundayEveningExam$, which takes as input an integer $n \geq 1$:
(see file for removed code)
Let $P(n)$ be the number of times the line "I don't like Sunday evening exams" is printed when running
algorithm $\SundayEveningExam(n)$. Which of the following is true for all $n \geq 1$?
(a)
$P(n) = 1 + \frac{n(n-1)}{2}$
(b)
$P(n) = \frac{n(n+1)}{2}$
(c)
$P(n) = 1 + \frac{n(n+1)}{2}$
(d)
$P(n) = \frac{n(n-1)}{2}$
Solution
On SundayEveningExam$ (n) $, the line \enquote{I don’t like Sunday evening exams} is printed n times
On SundayEveningExam$ (n-1) $, the line \enquote{I don’t like Sunday evening exams} is printed n-1 times
On SundayEveningExam$ (n-2) $, the line \enquote{I don’t like Sunday evening exams} is printed n-2 times
…
On SundayEveningExam$ (1) $, the line \enquote{I don’t like Sunday evening exams} is printed 1 time
$ P(n) = n + (n-1) + (n-2) + \text{…} + 1$
Using the 1st Formula given on the Exam Sheet, it translates the above to the following:
$ P(n) = \frac{n(n+1)}{2} $