Labs Homeworks |
## HW4## HW4: Due: Fri Feb 16, 11:59:59pmQ1. (20 points) Compute tight big-Oh bounds for the following recurrences: Q2. (10 points) Let \(A\) be an array of \(n\) integers, and let \(R\) be the range of values in \(A\), i.e., \(R = max(A)-min(A) \). Give an \(O(n + R)\) time algorithm to sort all the values in A. Q3. (15 points) Let A be an array of n distinct integers. Consider an algorithm to find the minimum value, where we pair up the elements, and retain the smaller of the values from each pair. This will result in an array of half the size (actually the resulting size will be \(\lceil n/2 \rceil\). We can then recursively apply the same approach, until we get a final array with just two elements. We compare these two values and return the minimum of those values as the answer. Answer the following questions: |

Page last modified on February 10, 2018, at 06:26 PM