Question

A recursive algorithm has a runtime t(n) that depends only on n, the input of size. t(1) = 1 and for an input size n, the algorithm solves two problems of size [n/2] and does extra work of n to get the output. What is the runtime of the algorithm?

1) t(n) = 2t(n/2) + n
2) t(n) = t(n/2) + n
3) t(n) = 2t(n/2) + 2n
4) t(n) = t(n/2) + 2n

Answer 1

The algorithm's runtime is represented by the recurrence relation t(n) = 2t(n/2) + n, which accounts for solving two subproblems of size n/2 and adding the extra work of size n.

Step-by-step explanation:

The runtime of the recursive algorithm given in the question is described by the following recurrence relation:

t(n) = 2t(n/2) + n

This is because for an input of size n, the algorithm divides the problem into two subproblems of size n/2, and the division '[n/2]' indicates that we take the floor of n/2 if n is not even. Each of these subproblems is solved recursively, leading to two instances of the runtime t(n/2). Additionally, there is some extra work done proportional to the size of the input, which is given as n. Therefore, the total work done for an input of size n is the work done for the two subproblems plus the extra work, resulting in the recurrence relation t(n) = 2t(n/2) + n.