Better algorithm (than using a dict) for enumerating pairs with a given sum.

Question

Given a number, I have to find out all possible index-pairs in a given array whose sum equals that number. I am currently using the following algo:

def myfunc(array,num):
    dic = {}
    for x in xrange(len(array)):  # if 6 is the current key,
        if dic.has_key(num-array[x]):  #look at whether num-x is there in dic
            for y in dic[num-array[x]]: #if yes, print all key-pair values
                print (x,y),
        if dic.has_key(array[x]):  #check whether the current keyed value exists
            dic[array[x]].append(x)  #if so, append the index to the list of indexes for that keyed value
        else:
            dic[array[x]] = [x]  #else create a new array

Will this run in O(N) time? If not, then what should be done to make it so? And in any case, will it be possible to make it run in O(N) time without using any auxiliary data structure?

Answer 1

Will this run in O(N) time?

Yes and no. The complexity is actually O(N + M) where M is the output size.
Unfortunately, the output size is in O(N^2) worst case, for example the array [3,3,3,3,3,...,3] and number == 6 - it will result in quadric number of elements needed to be produced.

However - asymptotically speaking - it cannot be done better then this, because it is linear in the input size and output size.