please solve

Problems (70 pts): 1. (20 pts) Draw the decision trees for quicksort, and merge sort on arrays of 3 elements and determine the worst-case numbers of comparisons performed by either sort. For quick sort, assume that the pivot is chosen in the same way as the partition algorithm in zyBook. 2. (20 pts) We proved in lecture that to sort n values by comparison only a minimal of log n! comparisons are needed in the worst case. This implies that to sort n = 4 values any comparison sort needs to perform at least log 4!, or 5 comparisons in the worst case. For each of the four comparison sorts, insertion, selection, quick and merge sort, explain why the sort performs at most 5 comparisons to sort an array of 4 numbers, or provide an example of array of size 4 on which the sort performs 6 or more comparisons. 3. (15 pts) Find an O(n)-time algorithm that on a sorted input array A of integers and a given integer intVal, finds two indices i and j, where A[i] * A0] = intVal. Explain why the running time of your algorithm is O(n). 4. (15 pts) Suppose that you have a program that can read through all posts within a given time period (eg, the last 7 days) on a social network web site (e.g., Facebook), and generate a list of pairs ( up) representing texts in all posts found, where i=1, 2, ..., and u, and prepresent the author username and the text content of the i-th post found, respectively. Describe an algorithm that outputs the list of usernames in the decreasing order of their total numbers of words posted among the posts described above. Analyze the running time of your algorithm. You may assume that the input of your algorithm is two arrays U and P that store the pairs (up) as defined above