Solve the Secretary Problem
Jelly, 13 bytes

L:Øe³ḣȯ-Ṁ&lt;i1ị


Definitely an O(n) algorithm, hopefully an O(n) implementation. Try it online!

How it works

L:Øe³ḣȯ-Ṁ&lt;i1ị  Main link. Argument: A (list of scores)

L              Get the length of A.
 :Øe           Divide the length by e, flooring the result.
    ³ḣ         Retrieve the that many scores from the beginning of A.
      ȯ-       Logical OR; replace an empty list with -1.
        Ṁ      Compute the maximum of those scores.
         &lt;     Compare each score in A with that maximum.
          i1   Find the first index of 1 (0 if not found).
            ị  Retrieve the element of A at that index (the last one if 0).