a. (15 Points) Write an algorithm that calculates the frequency of each number i

Question

a. (15 Points) Write an algorithm that calculates the frequency of each number in a given number array. In other words, you will count how many times each number appears in the array. For example, if the array is 1. A 1-12,3,-12, 4, 1, 1,-12, 1,-1,1,2,3, 4, 2, 3,-12 Then the output of your program should be N Count 2 4. 12 4 **To get full credit, your algorithm should be indented properly. b. (15 Points) What is the complexity of your solution? Perform a complexity analysis for the best case, worst case, and average case as shown in the video tutorials "**If your algorithm is not correct (eg. if it has major logical errors), max 5 credit is available for 1.b [ 34, 5, 8, 19, 23, 1, 30, 51 using merge sort and illustrate your (20 Points) Sort array A recursion calls it is shown in your lecture notes (sorting.pdf) 2. (30 Points) Please compute the following postfix expression using stack as shown in your textbook (page 106-107). For every scan, you need to show your stack and indicate the 3.

Explanation / Answer

Solution:

Note: The first question is done as per Chegg guidelines, please repost others.

Algorithm:

Insight: Since there are negative key values in the given array that is why I am using the brute-force method here otherwise it was possible to implement this in linear time (which is O(n)).

Running time:

The above algorithm is using two loops which are nested and they both are running n number of times which is same as the number of elements present in the array.

SO the time complexity of the above algorithm will be

T(n)= O(n^2)

b)

The time complexity will remain the same in all the case

Best case= O(n^2)

Average case= O(n^2)

Worst case= O(n^2)

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.