4
\$\begingroup\$

Devise an algorithm that will operate on a number x and a set of n distinct numbers such that in \$O(n \lg n)\$ time, the algorithm indicates whether or not there are two numbers in the set that have a product of x. Explain why your algorithm works.

My algorithm:

  1. Sort the set //\$ O(n \lg n)\$
  2. For every element in the set check if x % element =0 // \$O(n)\$
  3. If so check if the dividend x/element exists in the set // \$O(\lg n)\$
  4. If dividend exists and is not equal to element, the two numbers in the set (element and dividend) have a product of x.

This algorithm works because it only returns true when the condition(x=element*dividend where element and dividend are in the set) to be satisfied is met. And upon quick Analysis we can see that the algorithm is running at \$O(n\lg n)\$ for the sort and \$O(n)*(\lg n)\$ for checking if the two elements exists. Therefore it is running at \$O(n \lg n) + O(n \lg n) = O(2n \lg n) = O(n \lg n)\$

Can I have some feedback on my solution — whether you think it is correct or not and where you think it can be improved?

def findIfProdExists(x,items):
    items = mergeSort(items) # O(nlgn)
    for item in items:
        if(item!=0):
            if x%item ==0:
                if item!=x/item and find(x/item,items):  #binary Search O(lgn)
                    return True
    return False

def mergeSort(aList):
    size = len(aList)
    first = aList[:int(size/2)]
    second = aList[int(size/2):]

    if(size ==1):
         return aList
    if(size ==2):
        if(aList[1]<aList[0]):
            return list([aList[1],aList[0]])
        else:
            return aList
    else:
        return merge(mergeSort(first),mergeSort(second))


def merge(list1,list2):
        newList =[]
        i1 =0
        i2 =0
        while i1<len(list1) and i2 <len(list2) :
            if list1[i1] <list2[i2] :
                newList.append(list1[i1])
                i1+=1
            elif list1[i1]>list2[i2] :
                newList.append(list2[i2])
                i2+=1
            else:
                newList.append(list1[i1])
                i1+=1
        newList.extend(list1[i1:] +list2[i2:])
        return newList

def find(x,items):
    lo = 0
    hi = len(items)
    while lo<hi:
        mid = (lo + hi) // 2
        if x == items[mid]:
            return True
        elif x < items[mid]:
            hi = mid
        else:
            lo = mid + 1
    return False
\$\endgroup\$
  • \$\begingroup\$ Your program doesn't work for me: I get NameError: name 'mergeSort' is not defined. \$\endgroup\$ – Gareth Rees Mar 22 '15 at 10:40
  • \$\begingroup\$ Sorry about that I was just demonstrating the algorithm. I'll include the mergeSort Code so you may test. \$\endgroup\$ – imakeApps Mar 22 '15 at 10:58
  • 1
    \$\begingroup\$ Optionally you could use python's built in sort method on the list since from the python wiki wiki.python.org/moin/TimeComplexity it also has a time complexity of O(nlgn) \$\endgroup\$ – imakeApps Mar 22 '15 at 11:01
  • \$\begingroup\$ Thanks for that. But it still doesn't work for me. Now I get NameError: name 'find' is not defined. \$\endgroup\$ – Gareth Rees Mar 22 '15 at 11:17
  • 1
    \$\begingroup\$ The question said the set should have unique numbers \$\endgroup\$ – imakeApps Mar 22 '15 at 11:24
11
\$\begingroup\$

The algorithm description is good, but the implementation of find is \$ O(n) \$, so the overall runtime is actually \$ O(n^2) \$.

Detailed review follows:

  1. There are no docstrings. What does each function do? How do I call it? What does it return? Are there any constraints on the parameters, for example do the inputs have to be sorted? or do they have to be free of duplicates?

  2. It's not necessary in Python to have parentheses around the condition of if statement, and it's best to omit them.

  3. According to the analysis, find needs to be \$ O(\log n) \$, but the actual implementation is \$ O(n) \$. Here's a demonstration:

    >>> from timeit import timeit
    >>> for p in range(2, 8):
    ...     items = list(range(10**p))
    ...     '{:f}'.format(timeit(lambda:find(0, items), number=1))
    ...
    0.000012
    0.000022
    0.000077
    0.001386
    0.038858
    0.417670
    

    The reason for this is the copying in the recursive calls. In Python, the list slice items[mid:] has to be copied, and the time taken to do this is proportional to the number of items in the copy. See the time complexity page on the Python wiki.

  4. In order to avoid copying in find, it's best to keep indexes into the part of the sequence which might contain the item we're looking for:

    def find(x, items):
        """Return True if x is an element of the sequence items, assuming
        items is sorted.
    
        """
        lo = 0
        hi = len(items)
        while lo < hi:
            mid = (lo + hi) // 2
            if x == items[mid]: return True
            elif x < items[mid]: hi = mid
            else: lo = mid + 1
        return False
    
  5. Python has a built-in module bisect for binary search of sorted sequences, and using this module it's possible to write find like this:

    from bisect import bisect_left
    
    def find(x, items):
        """Return True if x is an element of the sequence items, assuming
        items is sorted.
    
        """
        i = bisect_left(items, x)
        return i < len(items) and items[i] == x
    
  6. The corrected version of find locates an element in a sorted list in time \$ O(\log n) \$. But it's possible to do better than that using a set. Set lookup has average complexity \$ O(1) \$.

  7. The implementation of merge goes into an infinite loop if list1 and list2 have a common item. This was easy for me to spot because there is an ifelif with no else at the end. When code has a sequence of conditions like this, it's always worth asking, "what happens if none of the conditions apply?"

  8. Python has a built-in function heapq.merge for merging sorted iterables into a single sorted iterator, and a built-in function sorted for sorting an iterable (using a variant of mergesort, as it happens). These are fast and well-tested implementations, and (except as an exercise) they should be used in preference to writing your own.

  9. In findIfProdExists the division x/item is computed twice in some cases. It would be better to compute it once and remember the value.

  10. In findIfProdExists the cheap test item!=x/item is computed after the expensive test find(x/item,items). It's usually best to compute cheap cases first so that if they fail the expensive test can be avoided altogether.

Putting all this together, I'd implement the algorithm like this:

def product_pair(x, items):
    """Return True if there is a pair of distinct elements in the iterable
    items whose product is x. Return False otherwise.

    """
    items = set(items)
    for item in items:
        if item != 0 and x % item == 0:
            y = x / item
            if y != item and y in items:
                return True
    return False
\$\endgroup\$
  • \$\begingroup\$ Quick question though set lookup has a time complexity of \$ O(1) \$ on average and \$ O(n) \$ in the worst case according to the Python wiki. Doesn't that mean that in the worst case the algorithm would have a quadratic running time ? \$\endgroup\$ – imakeApps Mar 22 '15 at 18:22
  • \$\begingroup\$ Yes, it's theoretically possible that many elements have the same hash, but in practice this is not worth worrying about unless the elements come from an untrusted source. \$\endgroup\$ – Gareth Rees Mar 22 '15 at 18:28
  • \$\begingroup\$ Ok I see, but after making the suggested fixes to merge and find functions, is your implementation still optimal compared to sorting then doing a binary search ? \$\endgroup\$ – imakeApps Mar 22 '15 at 18:31
  • \$\begingroup\$ Why not do a performance comparison and see for yourself? \$\endgroup\$ – Gareth Rees Mar 22 '15 at 18:33
  • \$\begingroup\$ think i can answer my own question. on average it would be because yours would have a Time complexity of \$ O(n) \$ right ? \$\endgroup\$ – imakeApps Mar 22 '15 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.