Results 1 to 1 of 1

Thread: Algorithms - find x+y = Z in AVERAGE CASE O(n)

  1. #1
    Aug 2009

    Algorithms - find x+y = Z in AVERAGE CASE O(n)

    So here is the exact question:

    Given a set S of n integers and another integer Z, determine whether or not there exist two elements x, y in S whose sum is exactly Z. Give an algorithm for this problem that runs in O(n) average-case time.

    Im rather confused on how to approach this problem, because of the average case limitation. Solving it in O(n^2) is simple, but i feel like a different method entirely is needed to solve this...

    My first inclination was something involving counting sort or a randomized partition sort (because that is what we have recently been covering in class). Can anyone point me in the right direction/explain this problem to me?

    Edit: I now know im supposed to use a data structure we've recently gone over, either a hash table or a binary search tree. Still the average case complexity is getting me... any help?

    Thanks for the help in advance!
    Last edited by Dfowj; October 11th 2009 at 08:20 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 9th 2010, 02:59 AM
  2. Find the average value
    Posted in the Calculus Forum
    Replies: 8
    Last Post: October 13th 2010, 08:32 PM
  3. Replies: 1
    Last Post: October 4th 2009, 03:27 PM
  4. find the average
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 23rd 2008, 03:46 AM

Search Tags

/mathhelpforum @mathhelpforum