Some problem of size n can be solved recursively by dividing it into 4 subproblems, where the size of each subproblem is n/3. Combining the results (at each step) requires linear time. Write a...

• Some problem of size n can be solved recursively by dividing it into 4 subproblems, where the size of each subproblem is n/3. Combining the results (at each step) requires linear time.

Write a recurrence relation (like the one we saw for MergeSort) that captures the

running time of this problem. Read about the
Master Theorem
to solve the recurrence.