Consider the divide-and-conquer approach -- MergeSort for sorting array with size m = 2^n. For each iteration, you

Divide: Divide the problem into 2 halves.

Conquer: Sort the two divided arrays using MergeSort recursively. If the arrays are of size 1,

Combine: Merge the sorted halves into a single array.

How many times will you perform the divide step in the procedure for the given array? (Each division into two sub-problems counts as 1.)

Select one:

a. n

b. (2^n)-1

c. 2^n

d. 2^(n-1)

What is the depth of the tree for the following recurrence relation :

T(n) = T(n/2) + (n)

(Give the closest answer)

Select one:

a. n

b. n / 2

c. log(n) + 1

d. 2 * n