1 Replies - 1379 Views - Last Post: 20 February 2007 - 11:38 AM

#1 Dnar  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 16-February 07

Designing algorithms with running times in mind

Posted 16 February 2007 - 06:57 PM

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

(B) 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 February 2007 - 07:00 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Designing algorithms with running times in mind

#2 jstephens  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 214
  • Joined: 07-November 05

Re: Designing algorithms with running times in mind

Posted 20 February 2007 - 11:38 AM

What Programming Language are you using?

Try something like this
int count = 0;
bool four_numbers_exists = false;
for ( int i = 0; i < a.length; i++)
{
  for(int e = 0; e < a.length; i++)
  {
	 if (a[i] ==  a[e])
	  {
		  count ++
		  if (count == 4)
			  four_numbers_exists = true;
	   }
	}
   count = 0
}



code will check each number against the top. If if finds four matches it will triger the 4 numbers exists variable. Then at the end it resets the count. for next loop.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1