There are 2 parts to this problem, the first part is one that I know how to do,
Part 1:
(a) Design an algorithm that takes an array A of n numbers and a number x. The algorithm returns TRUE if there are two numbers in A whose sum is x and FALSE otherwise. A number in A may be used twice in the sum. Justify the correctness and running time of your algorithm.
ANSWER:
1)Sort the array
2)Take X-A(1...n) and store into a temporary variable say TEMP
3)Do a binary search on TEMP
4)Return TRUE if TEMP is found
5)Else return FALSE
1) O(n log n)
2)O(n)
3)binary search is O(log n)
4)O(1)
5)O(1)
Therefore this algorithm is O(n log n)
PART 2
(
Same as part (a), but now the algorithm checks to see if there are exactly four numbers in A whose sum is x. A number in A may be used up to four times in the sum. This algorithm should take O(n^2 log n). Justify the correctness and running time of your algorithm.
On this part, I have put alot of effort into thinking about it, however, I can not seem to wrap my brain around it. I know based off the running time alone ie. O(n^2 log n), I need to search thru the array twice, and perform a binary search. The only thing I can think of is that I need to use part 1, twice and then combine the steps, but I still can not figure out how to do that either.
I started the algorithm like this and then sputtered completly out of ideas.
1.Sort the array O(n log n)
2.Take X-A(1...n) and store it into a temporary variable say TEMP O(n)
3.Take TEMP and subtract A(1...n) O(n)
So I suppose my question is, what can you tell me to guide me onto the right path here?
This is my first post here so be gentle to me
This post has been edited by Dnar: 16 Feb, 2007 - 06:00 PM
| 