Sorting
Page 1 of 111 Replies  1067 Views  Last Post: 10 April 2010  07:17 PM
#1
Sorting
Posted 04 April 2010  04:14 PM
You are given a set of n distinct numbers and you would like to know whether given a number
x, there are two elements of the set that sum to x. Describe an algorithm that runs in O(nlgn)
time that solves this problem, explaining why your algorithm works.
Replies To: Sorting
#2
Re: Sorting
Posted 04 April 2010  05:04 PM
I've actually written a snippet to solve a lessrestricted version of this problem, if you want to check it out. It tests to see if, given an int[] and a target, the target can be formed from the elements in the array.
Link: http://www.dreaminco...snippet5011.htm
#3
Re: Sorting
Posted 04 April 2010  06:25 PM
First part is sorting the numbers which takes O(nlogn).
Second part is matching. For each element i, subtract it from x and then search the set for an element xelem(i) using binarysearch O(log n). This part also takes O(nlogn) and therefore the algorithm runs in O(nlogn).
Knapsack is more general than this approach but maybe not as simple to understand. Also, knapsack is pseudopolynomial so you may not want to claim that it runs in O(nlogn).
#4
Re: Sorting
Posted 04 April 2010  06:26 PM
#5
Re: Sorting
Posted 04 April 2010  06:44 PM
#6
Re: Sorting
Posted 04 April 2010  06:55 PM
Quote
One run? Fibonacci search works very similarly to binary search, except it uses the fibonacci numbers to narrow down options, making it O(log(x)) vs. O(log(n)), so slightly more efficient.
#7
Re: Sorting
Posted 04 April 2010  10:04 PM
macosxnerd101, on 04 April 2010  04:04 PM, said:
I've actually written a snippet to solve a lessrestricted version of this problem, if you want to check it out. It tests to see if, given an int[] and a target, the target can be formed from the elements in the array.
Link: http://www.dreaminco...snippet5011.htm
Thanks macosxnerd101, it seems to be doing the job, but not in O(nlogn) time, but perhaps O(n) time, i'll probably try gloin's method and see if it works
#8
Re: Sorting
Posted 05 April 2010  03:44 AM
#9
Re: Sorting
Posted 05 April 2010  04:41 PM
So if you're going to compare radix with usual sorts like heapsort or mergesort, using the same criteria to denote "n", they will all have "n logn" complexity.
This post has been edited by Galois: 05 April 2010  04:43 PM
#10
Re: Sorting
Posted 08 April 2010  06:48 PM
#11
Re: Sorting
Posted 09 April 2010  09:06 AM
Radix sort starts by taking the first bit of all numbers and putting it in some bucket. This procedure is O(n). Then the radix sort does the same thing for the second bit, third bit, etc... How many times it's going to do it? The number of bits in the largest number. For simplicity just assume distinct numbers are chosen as n increases. Then the largest number after n choices will be at least n, which has logn bits.
If you constrain all your arithmetic to a fixed number of bits, then you can let k be a constant. As far as theory and bigO are concerned, Radix sort is still essentially an O(n logn) algorithm.
#12
Re: Sorting
Posted 10 April 2010  07:17 PM
