If you are given an unsorted list of n numbers, how long will it take to determine...

Question

If you are given an unsorted list of n numbers, how long will it take to determine whether there are three numbers x, y, and z in the list such that xy = z?

Answer 1

$O(n^2 \log n)$ is an upper bound. Your question says "numbers", which I'll assume means integers (because round-off worries complicate matters, though basically the same algorithm works). Also, your question doesn't require $x$ or $y$ to be unequal to $z$, nor does it require $x \neq y$ (more precisely, doesn't require that they be at different positions in the list $a$: $i \neq j$ where $x = a[i], y = a[j]$, which is sensible in case $a$ is e.g. (2, 4). Finally, I'll assume the list contains nonnegative integers. Generalization to signed integers is straightforward.

Here's a function which takes as parameter a list (array) a of nonnegative integers. If a contains values x, y, z such that x * y = z, the function returns a triple (i, j, k) such that x == a[i], y == a]j], z == a[k]. If a contains no such values, the function returns None.

Convention: assume indexes start at 0, so a = a[0:n] where n = length(a) (so a has no element at index n).

Assume that there's an existing function binsearch(arr, bottom, top, val) which takes a sorted array arr, integer indexes bottom, top, and a value val. This function returns an index j with bottom <= j < top if arr[k] == val, otherwise it returns -1 if val is not found in a[bottom:top]. Assume also that it implements binary search properly, so its time complexity is $O(\log_2 (top-bottom))$.

def find_triple(a):
    n = len(a)
    # deal with trivial cases
    if n == 0: return None
    if a[0] <= 1: return (0, 0, 0)

    # Sort a copy of a. 
    # This only costs O(n log n). Even O(n^2) is ok.
    a = sorted(a)

    for k in range(n):
        # See if there are i, j < k s.t. a[i]*a[j] == a[k]
        for i in range(k):
            # Assumption (loop invariant):
            #  for all ii < i, (a[k] // a[ii]) not in a[ii: k]
            q = a[k] // a[i]            # integer division
            if q * a[i] != a[k]:
                continue                # doesn't divide a[k] evenly; try next i
            j = binsearch(a, i, k, q)   # O(log i)
            if j != -1:                 # Found!
               return (i, j, k)
    return None

We sort a first, so that we can binary-search for quotients a[k] // a[i]. We can assume that sorted implements a sorting algorithm that's at worst $n^2$. Although we could assume better performance — $O(n \log n)$ by using, say, mergesort — for worst-case analysis it's unnecessary: the main loop of find_triple is worse than quadratic, so any not-insane sort will do. (Note: the above is valid Python, though you can just take it to be pseudocode. Python's builtin sorted function uses quicksort. I have a working version of find_triple, including a working binsearch.)

Given k in range(n), clearly the inner loop takes O(i log i). So the runtime of the main loop takes a constant factor times $$ \begin{align} \Sigma_{k=1}^n k \log k &\le \log n \: \Sigma_{k=1}^n k \\ &= \log n \frac {n (n+1)} 2 \\ &= O(n^2 \log n) \text{.} \end{align} $$ This dominates the time required to sort, so it's an upper bound for the whole function.

Answer 2

All values are assumed positive. (If not, positive and negative sublists can be handled separately.)

Sort the given list by increasing values, in time $O(n\log(n))$.

Then take a value $z$ from the array and initialize two indexes, $i_x$ and $i_y$, at the beginning and after then end of the array, corresponding to the elements $x$ and $y$. By convention, past the array $y=\infty$.

Ensure that $i_y$ is the smallest index such that $xy\ge z$ holds, by decrementing $i_y$ if necessary. If in addition $xy=z$, you are done for this $z$.

Repeatedly increment $i_x$ and decrement $i_y$ accordingly as long as $xy\ge z$. In the end, $i_x$ and $i_y$ will meet. If the condition $xy=z$ was never established, the search for this $z$ failed.

Thanks to monotonicity, the search for a $z$ takes time $O(n)$. Hence for all $z$, $O(n^2)$.

---

L= [3, 4, 5, 6, 21, 56, 78, 126, 280, 752]

L.append(999999)
for z in range(len(L) - 1):
    x= 0; y= len(L)
    while x < y:
        while x < y and L[x] * L[y - 1] >= L[z]:
            y-= 1
            if L[x] * L[y] == L[z]:
                print L[x], "*", L[y], "=", L[z]
        x+= 1

6 * 21 = 126
5 * 56 = 280