Home /
Expert Answers /
Computer Science /
17-a-describe-an-algorithm-to-determine-in-o-n-time-whether-an-arbitrary-array-a-1-pa871
(Solved): 17. (a) Describe an algorithm to determine in \( O(n) \) time whether an arbitrary array \( A[1 . ...
![17. (a) Describe an algorithm to determine in \( O(n) \) time whether an arbitrary array \( A[1 . . n] \) contains more than](https://media.cheggcdn.com/media/b3b/b3bafc36-2043-4c96-8e07-83393faab868/phpZmpw7e)
17. (a) Describe an algorithm to determine in \( O(n) \) time whether an arbitrary array \( A[1 . . n] \) contains more than \( n / 4 \) copies of any value. (b) Describe and analyze an algorithm to determine, given an arbitrary array \( A[1 . . n] \) and an integer \( k \), whether \( A \) contains more than \( k \) copies of any value. Express the running time of your algorithm as a function of both \( n \) and \( k \). Do not use hashing, or radix sort, or any other method that depends on the precise input values, as opposed to their order.
Expert Answer
(a). Let's assume an array of size n and check if the count of anyof the elements is more than the n/4. 1. Traverse the entire array, using a loop and use a hashmap to insert the elements