Creo que Qiaochu Yuan probablemente estaba bromeando, pero que en realidad está en la pista de la derecha, en el sentido de que la respuesta a la pregunta, en realidad, depende de lo teórico, físico, o modelo práctico de cálculo que tiene en mente.
No es descabellado imaginar modelos en los que un cálculo puede tomar 0 tiempo. Por ejemplo, usted podría tener una máquina de engranajes y palancas donde se configuran los engranajes en una posición determinada, como una entrada. Para obtener la salida, girar una manivela hasta que, después de la k revoluciones, se congela y no se enciende más. El número k es la potencia y el tiempo de ejecución. Es posible que k es cero, de modo que el tiempo de ejecución es cero. Por supuesto, esto no contar el tiempo que se tarda en entrar en la habitación, configurar las entradas, agarrar la manivela, etc. Pero no es completamente descabellado imaginar un útil modelo matemático en el que no se tienen en cuenta esas cosas como el tiempo de ejecución.
Tampoco es descabellado imaginar que podría haber más rápido y más rápido procesamiento de la información como n crece. A veces más información que hace que su tarea más fácil. Si yo soy un editor de libros y mi trabajo es tomar un montón de envíos, seleccione el mejor, y, a continuación, escribe el autor de una solicitud de las necesarias revisiones, mi trabajo podría ser más fácil cuando la pila es más alto, porque me puede permitirse el lujo de ser más exigente, probablemente voy a tener una mejor manuscrito, y no requieren de muchas revisiones.
Sin embargo, creo que hay un asunto fundamental que impide que nada de ser más rápido que O(1), que es de la que estamos hablando computación digital, no analógica. Si se trata de una máquina de Turing o una computadora de escritorio o el sistema de engranajes y palancas descrito anteriormente, una computadora digital normalmente opera en diferentes ciclos. Usted puede obtener un resultado de 0 ciclos, o en 1 ciclo, pero usted no puede tener la mitad de un ciclo. Si usted realmente desea tener O(1/n) de rendimiento, entonces tiene que haber alguna $n_o$ tal que para $n \ge n_o$ el tiempo de ejecución es de no más de 1/2 de un ciclo. Esto significa que para $n \ge n_o$ el cálculo siempre termina en 0 ciclos. El ejemplo de las palancas y engranajes que muestra que es posible para un cálculo para terminar en 0 ciclos, pero no puede haber tal cosa como un trivial de cálculo que siempre termina en 0 ciclos para la gran n. Para un cálculo como la que, simplemente, no sería necesario el uso de la máquina para $n \ge n_o$. Otra forma de decirlo es que si su cálculo siempre termina en 0 ciclos de $n \ge n_o$, luego de que su cómputo no sólo es más rápido que O(1), S(0), lo que significa que es trivial.
Así que creo que la respuesta es que el rendimiento más rápido que O(1) no es razonable que una computadora digital, y desde el big-O notación es realmente diseñado para los ordenadores digitales, no es obvio cómo plantear la cuestión en el caso de los equipos analógicos.
