ISourceCode

Make the frequent cases fast and the rare case correct

O(nlogn) algorithm for finding whether there exists a pair of elements from two different Sets (same size) that add up to a specified sum

To find if a pair of elements exists (one or more) from two sets of same size that equal a predefined sum.

import time
import random
def twosetsum(S1,S2):
        sum = 18000000
        n = m = len(S2)

        start = 0
        end = m-1
        while start < n and end >= 0 :  #O(n)
                if S1[start] + S2[end] > sum :
                        end = end-1
                elif S1[start] + S2[end] < sum :
                        start = start+1
                else:
                        return 1
start = time.strftime('%s')
S1 = range(1,9000001) #O(nlgn) sorted list
S2 = range(1,9000001) #O(nlgn) sorted list

value = twosetsum(S1,S2)

if value == 1 :
        print "Yes there is a pair"
else:
        print "No there is no pair"
end = time.strftime('%s')
time = int(end) - int(start)
print "Time to execute the Algorithm =", time ,"Second(s)"

OUTPUT:

labuser@ubuntu:~$ python twosetsum.py
Yes there is a pair
Time to execute the Algorithm = 8 Second(s)

Input : sum = 19000000
labuser@ubuntu:~$ python twosetsum.py
No there is no pair
Time to execute the Algorithm = 8 Second(s)

overall complexity O(n log n) + O(n log n) + O(n) = O(n log n)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: