Time Complexity bounds for approximate maximum of a sequence/array

Given a sequence x[1], x[2], ..., x[N] for a very large N. For any e, d > 0 find xhat such that with probability at least 1 - d, xhat lies within exp(e) factor of the maximum of x[1], x[2], ..., x[N].

Are there any results known about this that show precise dependence on the sequence, e and d? Are there any lower bounds on time complexity. I am not looking for worst case over all sequences. Any reference to the relevant literature would be appreciated.

Thanks in advance.