**Problem Detail:**

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?

My solution:

`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)

###### Asked By : user

#### Answered By : Yuval Filmus

Your algorithm doesn't work since you're analyzing it under some (suspect) random model, whereas the problem setters wanted a *worst case* guarantee. The worst case for you is that everything falls into the same bucket, and then you just get the usual $O(n\log n)$ guarantee.

Instead of your approach, I suggest trying to use the following observation:

After sorting, each value moves at most $2X$ positions.

As an example of why this is useful, note that you can find the minimum of the array in time $O(X)$ by looking only at the first $2X$ elements.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54210

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback