8

This is a homework question, so I would like to avoid complete answers and much prefer hints if possible.

Given an array of random integers A[1...x], the program should return the first y array elements in incrementing order where 1<=y<=sqrt(x). So, basically, given an array [5,9,2,8] and y=2, the program should return [2,5].

The "sort first, return first y items" answer is out the window since the best we can do is n*logn time with merge or quicksort. The answer thus has to make use of the fact that we only return at most sqrt(x) items, and the only other answer I have so far is doing a for-loop search for the minimum element in the array, removing the minimum from the array, stashing it in a new array, say B, and repeating the process on the now smaller modified version of A of length x-1, which gives us running time like so:

x + (x-1) + (x-2) + ... + (x-y)

That counts the number of for-loop iteration of the min-search, and gives us at most y or sqrt(x) iterations in the worst case scenario, and there are at most x items in the array. So we have sqrt(x)*x, which is better than O(n*logn) but still not quite O(n) :/.

Improve this question
7
  • 4
    Have you looked at bucket sort? When I see O(n) requirements it's the only thing that comes to mind. Commented Feb 2, 2011 at 2:34
  • "program should return the first y digits ". Maybe numbers? Commented Feb 2, 2011 at 2:36
  • @ruslki -- yes, i meant the first y array items. Fixing that now. Commented Feb 2, 2011 at 2:38
  • 4
    O(sqrt(x)*x) = O(x^(3/2)). Any polynomial time algorithm with exponent greater than 1 is asymptotically greater than an n log n algorithm. Commented Feb 2, 2011 at 2:45
  • Hence n log n is better than sqrt(n)*n. Commented Feb 2, 2011 at 2:47

5 Answers 5

Reset to default
9

Hint: Suppose you had an O(n) time algorithm to pick the yth element...

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

Then wouldn't I have to call it sqrt(x) times? That's still sqrt(x)*y.
@thezhaba: You are going in the wrong direction. For a further hint: think about the first step in quicksort.
Seems like people downvote without even knowing if what is written is right or wrong. Especially with incomplete answers with just hints, it is even more difficult to be sure if something is wrong. Ridiculous! :-)
Such algorithm would help. Another hint: prefiltering.
I don't see how this get how this can be better than O(n^(3/2))
|
0

Actually sqrt(x) grows faster than log(x), so O(x*sqrt(x)) is worse than O(n*log(x)). So you have not (yet) done better than sorting the whole list.

There are several ways to solve this problem. For one of them look at http://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms and look at all of the common sorting algorithms. Which algorithm can give you the first few elements most efficiently?

Improve this answer

1 Comment

There are heaps of good sorting algorithms on that page... :)
0

where 1<=y<=sqrt(x)

Note what this requirement gives you. If y ≤ √x, then y log y ≤ (√x log x) / 2 ∈ O(x½ log x) ⊂ O(x).

Sort-then-filter may be out the window, but filter-then-sort is acceptable.

Improve this answer

Comments

-1

For y, use the quick sort ideas, picking a random number and partition it into 2 parts. Part1(smaller) and part2(bigger).
If length of Part1 < y, then do the partition in Part2 with y' = y - len(Part1) If length of Part1 > y, then do the partition in Part1 with y' = y If length of Part1 == y, then sort Part1.

For partitioning, average should be almost in O(n) ( I can't approve it now, but it is very quick)( I will try to find some material for this part )..
Sort for y requires ylog(y) < sqrt(x) log ( sqrt(x) ) -> 1/2 * sqrt(x) * log(x) < 1/2 * sqrt(x) * sqrt(x) => 1/2 x.

Improve this answer

1 Comment

That's a very detailed and specific hint. And the running time is on average O(n). But your worst case performance is O(n*n), not O(n). I don't know whether that is sufficient for this homework problem.
-1

You only want a hint, right?

Read the comment by random_hacker very carefully in case you missed the big hint that he is giving. There is one algorithm for sorting an array where a tiny, tiny change will produce your algorithm.

In general, if y is not restricted to sqrt (x), you get an algorithm that works in O (x + y * log x), which is O (x) if y = O (x / log x), which is of course the case when y <= sqrt (x).

Improve this answer

1 Comment

hint @gnasher: have a peek at the dates, thezhaba may well be a lecturer by now.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.