City Guilds Model Questions Vol1 2020 Information Technology Question 42
Practice objective / multiple choice question 42 from the 2020 City Guilds Model Questions Vol1 Information Technology examination.
Consider the recursive function defined for non‑negative integers: \[\text{f}(n)=\begin{cases}1,& n\le 1\\[2mm]\text{f}(n-1)+2\,\text{f}\bigl(\lfloor n/2\rfloor\bigr),& n>1\end{cases}\] (a) Compute the value of \(\text{f}(8)\).\ (b) If the running time \(T(n)\) of the function satisfies \(T(n)=T(n-1)+T(\lfloor n/2\rfloor)+c\) for a constant \(c\), determine the asymptotic time complexity of the function using substitution or recursion‑tree reasoning.
Answer Options
About This Question
This is City Guilds Model Questions Vol1 2020 Information Technology Question 42. It is one of the objective questions from the 2020 City Guilds Model Questions Vol1 Information Technology examination.
Difficulty level: Hard .
Master the Exam!
You've seen a preview, but there are thousands more questions plus AI tutor to break down complex solutions.