Question

4 multiple choice 1 point consider an algorithm that divides a problem of size n into three subproblems of size n/3. if the base case is a problem of size 1, what is the maximum depth of the recursion tree (number of division steps) for an initial problem of size n? 3n n/3 log n log₃ n

Explanation:

Step1: Understand the recursion process

We start with a problem of size $N$ and divide it into sub - problems of size $\frac{N}{3}$ each time. We want to find out how many times we can do this division until we reach the base case of size 1.
Let the depth of the recursion tree be $d$. After the first division, the problem size becomes $\frac{N}{3}$, after the second division it becomes $\frac{N}{3^2}$, and after $d$ divisions, the problem size is $\frac{N}{3^d}$.

Step2: Set up the equation for the base - case

We know that at the base case, the problem size is 1. So we set up the equation $\frac{N}{3^d}=1$.
Solving for $d$:
\[

$$\begin{align*} \frac{N}{3^d}&=1\\ N&=3^d \end{align*}$$

\]
Taking the logarithm base 3 of both sides, we get $d = \log_3 N$.

Answer:

D. $\log_3 N$