a google internship exam algorithm

[tianqio]

given an positive array, find the biggest element c where c = a*b and a,b are elements of this array too. How fast you can?

[Yves M]

It depends on the range of the numbers (i.e. are they integers, doubles, some unbounded long numbers, etc.?) For ints, it's possible to do it in O(NlogN) in practise (although for N<10 it's technically possible to have a N^2 runtime, it doesn't enter into the O notation).

[tianqio]

the numbers are int. can you give a detail discription of your nlgn algorithm? thanks.

[xusword]

I do not know how others get O(n log n). I really do not think defining a range would help, big O notation wise...

The algorithms I came up with are all O(n square log n) in worst case. Some are clearly better then the other. (Due to the fact a, b, c are all intgers, we can define many trick to narrow the range of each variable)

Would the person who came up with n log n complexity care to share the algorithm with us?