CSE 551: Quiz 4 Solutions

1 Problem 1 Solve the following recurrence relation using any method. Provide your answer in big-O notation: T(n) = 2T( n 2 ) + log(n) for n > 1, 0 otherwise • T(n) = O(n) • T(n) = O(nlogn) • T(n) = O(n 2 ) • T(n) = O(logn) 1.1 Rationale This recurrence relation can be tricky to solve using iterative substitution or tree-based methods. It’s best to use the Master theorem here. Recall the form: T(n) = aT(n/b) + f(n) Since f(n) = log(n) = n  where  < log2(2) = 1, the Master method gives: T(n) = O(n log2(2)) = O(n) 2 Problem 2 Suppose we have a modified version of Merge-Sort that at each recursive level splits the array into two parts each of size 1 4 and 3 4 respectively. Also, assume the size of any given input array is a power of four. Give the asymptotic time complexity of this Merge-Sort variant.