how do you complete running times?
CSCI 3400 Homework 2 1. (25 Points) Write a C++ program that calculates the frequency of each number in the input number array. In other words, you will count how many times each number appears in the array. For example, if the array is A = [-12, 3, -12, 4, 1, 1, -12, 1, -1, 1, 2, 3, 4, 2, 3, -12] Then the output of your program should be NCount 42 33 22 14 -11 -124 a) (20 Points) What is the complexity of your solution? What is the best-case or worst-case scenario for this problem? b) (5 Points) Can this problem be solved in (nlogn) time? How? Please note that I am asking a C++ function generating this output. You do not have submit a source code. You can print the code and attach to your solutions. 2. (15 Points) Apply the merge sort to the following array. Show how the array is divided and then merged step by step. A = [64, 19, 26, 14, 63, 40, 80, 75] 3. (10 Points) Find the complexity of T(n) = 3T(n/3) + n using the recursion tree method (expand the T(n) into sub function calls and count additional costs). 4. (10 Points) Find the complexity of T(n) = 4*T(n/2) + 1 using master theorem. 5. (10 Points) Find the complexity of T(n) = 4*T(n/3) + using master theorem. 6. (15 Points) Answer following questions. True / False Reason 7. (15 Points) Fill the following table, show your work. Expression Dominant Term (?)