Let \(' 𝑛 '\) denote a positive integer. Suppose a function \(F\) is defined…
2022
Let \(' 𝑛 '\) denote a positive integer. Suppose a function \(F\) is defined as
\(f(n)=\left\{\begin{aligned} 0, & n=1 \\ f\left(\left\lfloor\frac{n}{2}\right\rfloor+1\right), & n>1\end{aligned}\right.\)
What is \(𝑓(25)\) ? and what does this function find?
- A.
\(4,\left\lfloor\log _{2} \mathrm{n}\right\rfloor\) - B.
\(14,\left\lfloor\log _{2} \mathrm{n}\right\rfloor\) - C.
\(4,\left\lfloor\frac{n}{2}\right\rfloor\) - D.
\(14,\left\lfloor\frac{n}{2}\right\rfloor\)
Attempted by 108 students.
Show answer & explanation
Correct answer: A
Answer: f(25) = 4; the function returns floor(log_2 n), i.e. the number of times you can repeatedly take floor(n/2) until reaching 1.
Step 1: Compute successive floor divisions starting from 25: 25 -> 12 -> 6 -> 3 -> 1. This requires 4 applications, so f(25) = 4.
Step 2: General justification: Let k = floor(log_2 n). Then 2^k <= n < 2^{k+1}. After k applications of taking floor(n/2) the value falls into [1,2), whose floor is 1. Therefore the number of applications required is k, so f(n) = floor(log_2 n).
Note: The intended recurrence that yields this result is f(1)=0 and f(n)=1+f(floor(n/2)) for n>1, which counts the number of halvings until reaching 1.
A video solution is available for this question — log in and enroll to watch it.