Question

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 number of division steps for an initial problem of size n? multiple choice 1 point 3n n/3 log n log3 n for an array of size n, a binary search algorithm performs at most log2 n + 1 comparisons in the worst case. multiple choice 1 point true false a divide - and - conquer algorithm divides a problem of size n into two subproblems of size n/2. if the base case is a problem of size 1, how many divisions (recursive calls to the division step, not total operations) are performed until the subproblems reach size 1 for an initial problem of size n? multiple choice 1 point log n log2 n n n/2

Explanation:

5.

Step1: Recall binary - search principle

In a binary search on an array of size $N$, at each step, the search space is halved.

Step2: Determine number of comparisons

The maximum number of steps (or comparisons) in the worst - case scenario to reduce the search space from size $N$ to 1 is $\lfloor\log_2 N
floor + 1$. So the statement is True.

Step1: Analyze divide - and - conquer recurrence

For a divide - and - conquer algorithm that divides a problem of size $N$ into two sub - problems of size $\frac{N}{2}$, we can use the recurrence relation. Let $T(N)$ be the number of operations. The recurrence is $T(N)=2T(\frac{N}{2})+f(N)$ (where $f(N)$ is the cost of combining sub - solutions). To get from a problem of size $N$ to sub - problems of size 1, if we start with $N$ and keep dividing by 2, the number of times we can divide is $\lfloor\log_2 N
floor$.

Answer:

True

6.