Algorithm question

This is a discussion on Algorithm question within the C++ Programming forums, part of the General Programming Boards category; Ok, first off I want to state that this is NOT a homework question! I'm wading through an algorithm book ...

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    Algorithm question

    Ok, first off I want to state that this is NOT a homework question! I'm wading through an algorithm book that I bought (pleasure reading if you can believe it!) and I'm having difficulty figuring out one of the problems in it, one of those star problems that are supposed to be harder than the rest. This question is only in chapter 3, so it shouldn't take a very high level algorithm. What the question asks for is given an unsorted array of n integers, and a value x, write an algorithm that tells you whether or not there exists two integers in the array who's sum is EXACTLY x.

    No problem, just iterate through the array with two nested loops that checks every possible configuration right? Nope, this sucker needs to run at a worst case (n log n) time which usually means something recursive/divide and conquer needs to be done. Straight iteration runs at n^2 time. I can't figure out how to do this.

    The best I can figure is to first recursively merge sort the array which is (n log n) time, then iterate through the array from the beginning and using divide and conquer to see if (x-array[i]) exists. This should be faster than the straight iteration, but I feel like there must be a better way since my algorithm has three separate functions, 2 at (n log n) time and one at n time. Anyone have any ideas?

    Sorry so confusing, if any of this needs clarification, don't hesitate to ask!

  2. #2
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511
    What book is this out of?

    Does the problem say it has to have a runtime of O(n log n)?
    Mr. C: Author and Instructor

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    The book is Intro to Algorithms by Cormer, and yes it has to have a run time of O(n log n)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Quick Algorithm Question
    By cjwenigma in forum C++ Programming
    Replies: 3
    Last Post: 11-01-2007, 11:39 AM
  2. Design layer question
    By mdoland in forum C# Programming
    Replies: 0
    Last Post: 10-19-2007, 05:22 AM
  3. STL algorithm question
    By Reggie in forum C++ Programming
    Replies: 1
    Last Post: 04-22-2003, 10:04 AM
  4. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 09:22 PM
  5. More a math question than an algorithm
    By Gustaff in forum C Programming
    Replies: 1
    Last Post: 01-28-2003, 01:10 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21