• Design/Analysis of Algorithms

Design/Analysis of Algorithms

please show all work with steps

Question #7 (16 points) Consider the following recurrence relation: if n=1 T(n) 27 (n 1) +n if n > 1 Provide clear, concise answers to each of the following related questions. . (2 points). Assume this recurrence describes the runtime of a divide- and-conquer algorithm. If you looked at the body of a function that implemented this algorithm, how many recursive calls should it contain? (2 points). Assume this recurrence describes the runtime of a divide- and-conquer algorithm. If you looked at the body of a function that implemented this algorithm, how much smaller are the subproblems solved by the recursive calls? (12 points). Determine an upper-bound for this recurrence and prove that bound formally (i.e., not with a picture)