Question

TEXTBOOK: DISCRETE MATHEMATICS FOR COMPUTER SCIENTISTS

Clifford Stein Columbia University

Robert L. Drysdale DartmouthCollege

Kenneth Bogart

Thank you in advance!

Draw a recursion tree diagram for (47(n/4) +n if n > 2, Use it to find the exact solution to the recurrence. Assume n is a power of 4. T(n) if n = 1. You don't really need to draw the tree, but what's important and necessary is for you to draw the table with the following columns: Number of Problems Problem Size Work per Level (Reference diagram 4.6 in the textbook)

Answer 1

The recurrence relation is used to draw a recursive tree diagram. Using that, the final time complexity of the recurrence relation is found out. We find that the complexity comes out to be O(n * log₄n). The derivation of the answer and the required table is filled and is shown in the photos below.