Answer the following problem and show how

30. The recurrence relation for the worst-case complexity W(n) of the sorting algorithm Mergesort for na power of 2 is given by: a) Win-win-1) + n. Initial Condition (1)-0 b) W(n)=2W(n-1) + n. Initial Condition (1) = 0 c) W(n)2W(n/2) + 1. Initial Condition (1) = 0 d) Win-Win/2) + n-1. Initial Condition w(1)-0 e) Win) 2W(n/2) + n-1. Initial Condition (1) = 0 31. The average number of updates in computing the maximum element in a list of size n for a uniform distribution is approximately: a) (logan)/2 b) logan c) Inn d) n/2 e) nlogan 32. A data structure that can be used to obtain a non-recursive version of a recursive algorithm: a) stack b) queue c) priority queue d) 2-tree e) balanced tree 33. The worst-case complexity W(n) of a given algorithm is defined as: a) The fewest basic operations performed b) The most basic operations performed c) The most basic operations performed for an input of size d) The worst performance of the algorithm e) The expected performance over all inputs of size n 34. Which traversal outputs the nodes of a binary search tree in sorted order: a) Preorder Traversal b) Inorder Traversal c) Postorder Traversal d) Phat Traversal e) None of the above 35. The formal definition of an algorithm uses the following concept: a) Algorithm machine b) Turing machine c) Phat machine d) Al machine e) Scooby Doo mystery machine