Consider the recursive function defined for non‑negative integers:

$$
f(n)=\begin{cases}
1, & n\le 1\[2mm]
f(n-1)+2\,f(n-2), & n1
\end{cases}
$$

(a) Compute the value of $f(5)$.
(b) State the asymptotic time‑complexity of a naïve implementation that follows this definition, using big‑O notation.

Question

Consider the recursive function defined for non‑negative integers:

$$
 f(n)=\begin{cases}
 1, & n\le 1\[2mm]
 f(n-1)+2\,f(n-2), & n>1
 \end{cases}
$$

(a) Compute the value of $f(5)$.  
(b) State the asymptotic time‑complexity of a naïve implementation that follows this definition, using big‑O notation.

Accepted Answer

f(5)=21; time complexity O(2^n)

City Guilds Model Questions Vol1 2023 Information Technology Question 14

Answer Options

About This Question

Master the Exam!