If given a sorted array of n distinct positive integers. And each element is incremented or decremented by a number between 0 and X. For positive integer X that is a function of n.
Formulate an algorithm that takes the inc/dec array and sort it. Make the run time O(n) when X is constant.
I am unsure with my solution. Firstly, I just choose an random number of buckets... 10. The proof seemed to work out. Is there a way to prove that using X(the variable from above) number of buckets will be better?
In addition, is there a way to utilize the fact the array has been sorted prior to being augmented?
1. Find the minimum and maximum of the array by iteratively going through the array O(n) 2. Create intervals for the k buckets (k = number of buckets) int interval int k = 10 interval = (Max – Min + 1)/k 3. Assign each element to the bucket based on the interval O(n) 4. Sort each bucket if there is ni elements in each ith bucket the sorting using randomized quicksort S(ni) = O(nilogni) 5. Combine all the elements O(n) Runtime Analysis: • The time to sort every bucket will be as follows: • We assume the elements are uniformly distributed. Thus n/k elements in each bucket.
Since k = n/10, T(n) = n log(10) = O(n)