¿Se clasificaría esto como un algoritmo O (1) para "¡Hola, mundo!" ??

public class Hello1
{
   public static void Main()
   {
      DateTime TwentyYearsLater = new DateTime(2035,01,01);
      while ( DateTime.Now < TwentyYearsLater )
      { 
          System.Console.WriteLine("It's still not time to print the hello ...");
      }
      System.Console.WriteLine("Hello, World!");
   }
}

Estoy pensando en usar el

DateTime TwentyYearsLater = new DateTime(2035,01,01);
while ( DateTime.Now < TwentyYearsLater )
{ 
   // ... 
}

fragmento de código como un bucle ocupado para incluirlo como una broma cada vez que alguien solicita un algoritmo de cierta complejidad. ¿Sería esto correcto?

La notación Big O en este contexto se utiliza para describir una relación entre el tamaño de la entrada de una función y el número de operaciones que se deben realizar para calcular el resultado de esa entrada.

Su operación no tiene entrada con la que se pueda relacionar la salida, por lo que usar la notación Big O no tiene sentido. El tiempo que tarda la operación es independiente de las entradas de la operación (que es ... ninguna). Dado que no existe una relación entre la entrada y la cantidad de operaciones realizadas, no puede usar Big O para describir esa relación inexistente

La notación Big-O significa aproximadamente 'dada una operación en una cantidad de trabajo, N, ¿cuánto tiempo de cálculo, proporcional a N, toma el algoritmo?'. Por ejemplo, ordenar una matriz de tamaño N puede tomar N ^ 2, Nlog (N), etc.

Esto no tiene una cantidad de datos de entrada sobre los que actuar. Entonces no lo es O(anything).

Peor aún; esto no es técnicamente un algoritmo. Un algoritmo es un método para calcular el valor de una función matemática; las funciones matemáticas son un mapeo de una entrada a una salida. Dado que esto no toma ninguna entrada y no devuelve nada, no es una función, en el sentido matemático. De wikipedia:

Un algoritmo es un método eficaz que se puede expresar en una cantidad finita de espacio y tiempo y en un lenguaje formal bien definido para calcular una función. Comenzando desde un estado inicial y una entrada inicial (quizás vacía), las instrucciones describen un cálculo que, cuando se ejecuta, avanza a través de un número finito de estados sucesivos bien definidos, produciendo eventualmente "salida" y terminando en un estado final final.

Lo que esto es, técnicamente, es un sistema de control. De wikipedia;

Un sistema de control es un dispositivo, o conjunto de dispositivos, que administra, ordena, dirige o regula el comportamiento de otros dispositivos o sistemas.

Para las personas que desean una respuesta más detallada sobre la diferencia entre funciones matemáticas y algoritmos, y las capacidades más poderosas de las computadoras para hacer cosas con efectos secundarios como salida de consola, mostrar gráficos o controlar robots, lea este documento en el Fuerte hipótesis de Church-Turing

Resumen

La visión clásica de la computación posiciona la computación como una transformación de caja cerrada de entradas (números racionales o cadenas finitas) a salidas. Según la visión interactiva de la computación, la computación es un proceso interactivo continuo en lugar de una transformación basada en funciones de una entrada a una salida. Específicamente, la comunicación con el mundo exterior ocurre durante el cálculo, no antes ni después. Este enfoque cambia radicalmente nuestra comprensión de qué es la computación y cómo se modela.

La aceptación de la interacción como un nuevo paradigma se ve obstaculizada por la Strong Church-Turing Thesis (SCT), la creencia generalizada de que las máquinas de Turing (TM) capturan todos los cálculos, por lo que los modelos de computación más expresivos que las TM son imposibles. En este artículo, mostramos que SCT reinterpreta la Tesis original de Church-Turing (CTT) de una manera que Turing nunca pretendió; su equivalencia comúnmente asumida con el original es un mito. Identificamos y analizamos las razones históricas de la creencia generalizada en la SCT. Solo aceptando que es falso podemos comenzar a adoptar la interacción como un paradigma alternativo de computación

No, su código tiene una complejidad de tiempo de O(2^|<DeltaTime>|),

Para una correcta codificación de la hora actual.
Por favor, primero déjame disculparme por mi inglés.

Qué es y cómo funciona Big O en CS

La notación Big O no se utiliza para vincular la entrada de un programa con su tiempo de ejecución .
La notación Big O es, dejando atrás el rigor, una forma de expresar la relación asintótica de dos cantidades .

En el caso del análisis de algoritmos, estas dos cantidades no son la entrada (para lo cual primero se debe tener una función de "medida") y el tiempo de ejecución.
Son la longitud de la codificación de una instancia del problema ¹ y una métrica de interés.

Las métricas de uso común son

1. El número de pasos necesarios para completar el algoritmo en un modelo de cálculo dado.
2. El espacio requerido, si existe tal concepto, por el modelo de computación.

Se asume implícitamente una TM como modelo, de modo que el primer punto se traduce en el número de aplicaciones de la función de transición ² , es decir, "pasos", y el segundo traduce el número de celdas de cinta diferentes escritas al menos una vez .

¿También a menudo se asume implícitamente que podemos usar una codificación relacionada polinomialmente en lugar de la original, por ejemplo, una función que busca una matriz de principio a fin tiene O(n)complejidad a pesar del hecho de que una codificación de una instancia de dicha matriz debe tener una longitud de n*b+(n-1)donde bes el número (constante) de símbolos de cada elemento. Esto se debe a que bse considera una constante del modelo de cálculo y, por lo tanto, la expresión anterior y nson asintóticamente iguales.

Esto también explica por qué un algoritmo como Trial Division es un algoritmo exponencial a pesar de ser esencialmente un for(i=2; i<=sqr(N); i++)algoritmo similar ³ .

Mira esto .

Esto también significa que la notación O grande puede usar tantos parámetros como sea necesario para describir el problema, ¿no es inusual tener un parámetro k para algunos algoritmos?

Así que no se trata de la "entrada" o de que "no hay entrada".

Estudio de caso ahora

La notación Big O no cuestiona su algoritmo, solo asume que sabe lo que está haciendo. Es esencialmente una herramienta aplicable en todas partes, incluso en algoritmos que pueden ser deliberadamente engañosos (como el suyo).

Para resolver su problema, utilizó la fecha actual y una fecha futura, por lo que deben ser parte del problema de alguna manera; en pocas palabras: son parte de la instancia del problema.

Específicamente la instancia es:

<DeltaTime>

Donde el <>significa cualquier codificación, no patológica, de elección.

Consulte a continuación para obtener aclaraciones muy importantes .

Entonces, su gran tiempo de complejidad O es justo O(2^|<DeltaTime>|), porque realiza una serie de iteraciones que dependen del valor del tiempo actual. No tiene sentido poner otras constantes numéricas ya que la notación asintótica es útil ya que elimina constantes (por ejemplo, el uso de no O(10^|<DeltaTime>|*any_time_unit)tiene sentido).

Donde esta la parte complicada

Hicimos una suposición importante arriba: que el modelo de cálculo reifica ^{5 el} tiempo, y por tiempo me refiero al tiempo físico (¿real?). No existe tal concepto en el modelo computacional estándar, una MT no conoce el tiempo, vinculamos el tiempo con el número de pasos porque así es como funciona nuestra realidad ⁴ .

En su modelo, sin embargo, el tiempo es parte del cálculo, puede usar la terminología de personas funcionales diciendo que Main no es puro, pero el concepto es el mismo.

Para entender esto, uno debe tener en cuenta que nada impide que el Framework use un tiempo falso que se ejecuta dos, cinco, diez veces más rápido que el tiempo físico. De esta manera, su código se ejecutará en "la mitad", "una quinta parte", "una décima parte" del "tiempo".

Esta reflexión es importante para elegir la codificación de <DeltaTime>, esta es esencialmente una forma condensada de escribir <(CurrentTime, TimeInFuture)>. Dado que el tiempo no existe a priori, la codificación de CurrentTime podría muy bien ser la palabra Now (o cualquier otra opción) el día anterior podría codificarse como Yesterday , rompiendo la suposición de que la duración de la codificación aumenta como el tiempo físico avanza (y el de DeltaTime disminuye)

Tenemos que modelar correctamente el tiempo en nuestro modelo computacional para hacer algo útil.

La única opción segura que podemos hacer es codificar marcas de tiempo con longitudes crecientes (pero sin usar unario) a medida que avanza el tiempo físico. Esta es la única propiedad verdadera del tiempo que necesitamos y la que la codificación necesita capturar. Es solo con este tipo de codificación que a su algoritmo se le puede dar una complejidad de tiempo.

Su confusión, si la hay, surge del hecho de que la palabra tiempo en las frases "¿Cuál es su complejidad temporal ?" y '¿Cuánto tiempo llevará?' significa cosas muy muy diferentes

Lamentablemente, la terminología usa las mismas palabras, pero puedes intentar usar "complejidad de pasos" en tu cabeza y volver a hacerte tu pregunta, espero que te ayude a entender que la respuesta realmente es ^ _ ^

¹ Esto también explica la necesidad de un enfoque asintótico, ya que cada instancia tiene una longitud diferente, pero no arbitraria.
² Espero estar usando el término en inglés correcto aquí.
³ También es por eso que a menudo encontramos log(log(n))términos en matemáticas.
⁴ Id est, un paso debe ocupar un intervalo de tiempo finito, pero no nulo, ni desconectado.
⁵ Esto significa que el modo computacional como conocimiento del tiempo físico en él, es decir, puede expresarlo con sus términos. Una analogía es cómo funcionan los genéricos en el marco .NET.

Aunque hay un montón de buenas respuestas aquí, permítanme reformularlas un poco.

La notación Big-O existe para describir funciones . Cuando se aplica al análisis de algoritmos, esto requiere que primero definamos alguna característica de este algoritmo en términos de una función . La opción común es considerar el número de pasos en función del tamaño de entrada . Como se señaló en otras respuestas, crear tal función en su caso parece extraño, porque no hay una "entrada" claramente definida. Sin embargo, todavía podemos intentar hacerlo:

• Podemos considerar su algoritmo como una función constante que toma cualquier entrada de cualquier tamaño, la ignora, espera una cantidad fija de tiempo y finaliza. En este caso, su tiempo de ejecución es f (n) = const , y es un algoritmo de tiempo O (1). Esto es lo que esperabas escuchar, ¿verdad? Sí, técnicamente es un algoritmo O (1) .
• Podemos considerar TwentyYearsLatercomo el parámetro de interés similar al "tamaño de entrada". En este caso, el tiempo de ejecución es f (n) = (nx) donde x es el "momento actual" en el momento de la invocación. Visto de esta manera, es un algoritmo de tiempo O (n). Espere este contraargumento cada vez que vaya mostrando su algoritmo técnico O (1) a otras personas.
• Oh, pero espere, si k =TwentyYearsLater es la entrada, entonces su tamaño n es, en realidad, el número de bits necesarios para representarlo, es decir, n = log (k) . La dependencia entre el tamaño de la entrada n y el tiempo de ejecución es, por lo tanto, f (n) = 2 ^ n - x . ¡Parece que su algoritmo se ha vuelto exponencialmente lento! Ugh.
• Otra entrada al programa es, de hecho, el flujo de respuestas dadas por el sistema operativo a la secuencia de DateTime.Nowinvocaciones en el bucle. De hecho, podemos imaginar que toda esta secuencia se proporciona como entrada en el momento en que ejecutamos el programa. Entonces se puede considerar que el tiempo de ejecución depende de la propiedad de esta secuencia, es decir, su longitud hasta el primer TwentyYearsLaterelemento. En este caso, el tiempo de ejecución es nuevamente f (n) = ny el algoritmo es O (n) .

Pero, de nuevo, en su pregunta ni siquiera dijo que estaba interesado en el tiempo de ejecución. ¿Y si te refieres al uso de la memoria? Dependiendo de cómo modele la situación, puede decir que el algoritmo es O (1) -memory o, quizás, O (n) -memory (si la implementación de DateTime.Nowrequiere realizar un seguimiento de toda la secuencia de invocación de alguna manera).

Y si su objetivo era llegar a algo absurdo, ¿por qué no va con todo y dice que está interesado en cómo el tamaño del código del algoritmo en píxeles en la pantalla depende del nivel de zoom elegido? Esto podría ser algo como f (zoom) = 1 / zoom y puedes declarar con orgullo que tu algoritmo tiene un tamaño de píxel de O (1 / n) .

Tengo que estar un poco en desacuerdo con Servy. Hay una entrada para este programa, incluso si no es obvia, y ese es el momento del sistema. Esto podría ser un tecnicismo que no pretendía, pero su TwentyYearsFromNowvariable no está a veinte años del tiempo del sistema ahora , está asignada estáticamente al 1 de enero de 2035.

Entonces, si toma este código y lo ejecuta en una máquina que tiene una hora del sistema del 1 de enero de 1970, tardará 65 años en completarse, independientemente de lo rápido que sea la computadora (puede haber alguna variación si su reloj es defectuoso ). Si toma este código y lo ejecuta en una máquina que tiene una hora de sistema del 2 de enero de 2035, se completará casi instantáneamente.

Yo diría que su entrada,, nes January 1st, 2035 - DateTime.Now, y es O (n).

Luego también está la cuestión del número de operaciones. Algunas personas han notado que las computadoras más rápidas alcanzarán el ciclo más rápido, lo que provocará más operaciones, pero eso es irrelevante. Cuando trabajamos con notación Big-O, no consideramos la velocidad del procesador o el número exacto de operaciones. Si tomó este algoritmo y lo ejecutó en una computadora, y luego lo ejecutó nuevamente, pero durante 10 veces más en la misma computadora, esperaría que la cantidad de operaciones crezca en el mismo factor de 10 veces.

En cuanto a esto:

Estoy pensando en usar el fragmento de código [código redactado] como un bucle ocupado para ponerlo como una broma cada vez que alguien pide un algoritmo de cierta complejidad. ¿Sería esto correcto?

No en realidad no. Otras respuestas han cubierto esto, así que solo quería mencionarlo. Por lo general, no puede correlacionar los años de ejecución con ninguna notación de O grande. P.ej. No hay forma de decir 20 años de ejecución = O (n ^ 87) o cualquier otra cosa para el caso. Incluso en el algoritmo que proporcionó, podría cambiar el TwentyYearsFromNowaño 20110, 75699436 o 123456789 y el gran O sigue siendo O (n).

El análisis Big-O se ocupa de la cantidad de procesamiento involucrado a medida que la cantidad de datos que se procesan aumenta sin límite.

Aquí, en realidad solo se trata de un único objeto de tamaño fijo. Como tal, la aplicación del análisis big-O depende en gran medida (¿principalmente?) De cómo defina sus términos.

Por ejemplo, podría referirse a la impresión de resultados en general e imponer una espera tan larga que cualquier cantidad razonable de datos se imprimiría / se imprimirá precisamente en el mismo período de tiempo. Sin embargo, también debe agregar un poco más en forma de definiciones un tanto inusuales (si no totalmente erróneas) para llegar muy lejos; en particular, el análisis de big-O generalmente se define en términos de la cantidad de operaciones fundamentales necesarias para llevar a cabo un análisis. tarea particular (pero tenga en cuenta que la complejidad también se puede considerar en términos de cosas como el uso de memoria, no solo el uso de CPU / operaciones realizadas).

Sin embargo, la cantidad de operaciones fundamentales generalmente se traduce bastante cerca del tiempo que se toma, por lo que no es una exageración tratar las dos como sinónimos. Desafortunadamente, sin embargo, todavía estamos atrapados con esa otra parte: la cantidad de datos que se procesan aumenta sin límite. Siendo ese el caso, ningún retraso fijo que pueda imponer realmente funcionará. Para equiparar O (1) con O (N), tendría que imponer un retraso infinito para que cualquier cantidad fija de datos tardara una eternidad en imprimirse, tal como lo haría una cantidad infinita de datos.

big-O relativo a qué?

Pareces intuir que twentyYearsLateres una "entrada". Si de hecho escribiste tu función como

void helloWorld(int years) {
   // ...
}

Sería O (N) donde N = años (o simplemente decir O(years)).

Yo diría que su algoritmo es O (N) en relación con cualquier número que escriba en la línea de código que comienza twentyYearsLater =. Pero la gente generalmente no considera los números en el código fuente real como entrada. Pueden considerar la entrada de la línea de comandos como la entrada, o la entrada de la firma de la función como la entrada, pero lo más probable es que no el código fuente en sí. Eso es lo que está discutiendo con su amigo: ¿es esta la "entrada"? Configura su código de manera que intuitivamente parezca una entrada, y definitivamente puede preguntar su gran tiempo de ejecución O con respecto al número N en la línea 6 de su programa, pero si usa una opción no predeterminada como entrada, realmente necesita ser explícito al respecto.

Pero si considera que la entrada es algo más habitual, como la línea de comando o la entrada a la función, no hay ninguna salida y la función es O (1). Se necesitan veinte años, pero como big-O no cambia hasta un múltiplo constante, O (1) = O (veinte años).

Pregunta similar: cuál es el tiempo de ejecución de:

void sortArrayOfSizeTenMillion(int[] array)

Suponiendo que hace lo que dice y la entrada es válida, y el algoritmo aprovecha una clasificación rápida o una clasificación de burbujas o cualquier cosa razonable, es O (1).

Este "algoritmo" se describe correctamente como O (1) o tiempo constante. Se ha argumentado que no hay entrada para este programa, por lo tanto, no hay N para analizar en términos de Big Oh. No estoy de acuerdo con que no haya entrada. Cuando esto se compila en un ejecutable y se invoca, el usuario puede especificar cualquier entrada de longitud arbitraria. Esa longitud de entrada es N.

El programa simplemente ignora la entrada (de cualquier longitud), por lo que el tiempo necesario (o el número de instrucciones de la máquina ejecutadas) es el mismo independientemente de la longitud de la entrada (dado el entorno fijo = hora de inicio + hardware), por lo tanto O (1 ).

Una cosa que me sorprende no se ha mencionado todavía: ¡la notación Big-O es un límite superior!

El problema que todos han notado es que no hay una N que describa las entradas al algoritmo, por lo que no hay nada con qué hacer un análisis de O grande. Sin embargo, esto se mitiga fácilmente con algunos trucos básicos, como aceptar int ne imprimir las nhoras de "Hola mundo" . Eso evitaría esa queja y volvería a la pregunta real de cómo funciona esa DateTimemonstruosidad.

No hay garantía real de que el ciclo while terminará alguna vez. Nos gusta pensar que tiene que hacerlo en algún momento, pero considere que DateTime.nowdevuelve la fecha y hora del sistema . En realidad, no hay garantía de que esto esté aumentando monótonamente. Es posible que algún mono entrenado patológicamente cambie constantemente la fecha y la hora del sistema hasta el 21 de octubre de 2015 a las 12:00:00 UTC hasta que alguien le dé al mono unos zapatos de ajuste automático y un hoverboard. ¡Este bucle puede durar una cantidad infinita de tiempo!

Cuando realmente profundiza en la definición matemática de notaciones con gran O, son límites superiores. Demuestran el peor de los casos, por improbable que sea. El peor escenario * aquí es un tiempo de ejecución infinito, por lo que nos vemos obligados a declarar que no hay una notación O grande para describir la complejidad del tiempo de ejecución de este algoritmo. No existe, al igual que el 1/0 no existe.

* Editar: de mi discusión con KT, no siempre es válido suponer que el escenario que estamos modelando con la notación Big-O es el peor de los casos. En la mayoría de los casos, si un individuo no especifica qué caso estamos usando, su intención es explorar el peor de los casos. Sin embargo, puede hacer un análisis de complejidad big-O en el mejor tiempo de ejecución.

La complejidad se utiliza para medir la "potencia" computacional en términos de tiempo / espacio. La notación Big O se usa para comparar qué problemas son "computables" o "no computables" y también para comparar qué soluciones -algoritmos- son mejores que otras. Como tal, puede dividir cualquier algoritmo en dos categorías: los que se pueden resolver en tiempo polinómico y los que no.

Problemas como el tamiz de erathostene son O (n ^ exp) y, por lo tanto, se pueden resolver para valores pequeños de n. Son computables, pero no en tiempo polinomial (NP) y, por lo tanto, cuando se le pregunta si un número dado es primo o no, la respuesta depende de la magnitud de dicho número. Además, la complejidad no depende del hardware, por lo que tener ordenadores más rápidos no cambia nada ...

Hello World no es un algoritmo y, como tal, no tiene sentido intentar determinar su complejidad, que no es ninguna. Un algoritmo simple puede ser algo como: dado un número aleatorio, determine si es par o impar. Ahora bien, ¿importa que el número dado tenga 500 dígitos? No, porque solo tienes que comprobar si el último dígito es par o impar. Un algoritmo más complejo sería determinar si un número dado se divide uniformemente entre 3. Aunque algunos números son "fáciles" de calcular, otros son "difíciles" y esto se debe a su magnitud: compare el tiempo que lleva determinar el remanente entre un número de un dígito y otro de 500 dígitos.

Un caso más complejo sería decodificar un texto. Tiene una serie aparentemente aleatoria de símbolos que también sabe que están transmitiendo un mensaje para quienes tienen la clave de descifrado. Digamos que el remitente usó la tecla de la izquierda y su Hola mundo leería: Gwkki Qieks. La solución "martillo grande, sin cerebro" produciría todas las combinaciones para esas letras: desde Aaaa hasta Zzzz y luego buscaría en un diccionario de palabras para identificar qué palabras son válidas y compartir las dos letras comunes en la cifra (i, k) en la misma posición. ¡Esta función de transformación es lo que mide Big O!

La mayoría de la gente parece perder dos cosas muy importantes.

1. El programa hace tener una entrada. Es la fecha / hora codificada de forma rígida con la que se compara la hora del sistema. Las entradas están bajo el control de la persona que ejecuta el algoritmo y la hora del sistema no. Lo único que puede controlar la persona que ejecuta este programa es la fecha / hora que ha codificado en la comparación.

2. El programa varía según el valor de entrada , pero no el tamaño del conjunto de entrada , que es de lo que se ocupa la notación O grande.

Por lo tanto, es indeterminado, y la mejor notación 'gran-O' para este programa probablemente sería O (nulo), o posiblemente O (NaN).

Todos han señalado correctamente que no define N , pero la respuesta es no bajo la interpretación más razonable. Si N es la longitud de la cadena que estamos imprimiendo y "¡hola, mundo!" es solo un ejemplo, como podríamos inferir de la descripción de esto como un algoritmo "para" hello, world!, entonces el algoritmo es O ( N ), porque es posible que tenga una cadena de salida que tarde treinta, cuarenta o cincuenta años en imprimirse, y Solo agrego un tiempo constante a eso. O ( kN + c ) ∈ O ( N ).

Apéndice:

Para mi sorpresa, alguien está cuestionando esto. Recuerde las definiciones de gran O y gran Θ. Suponga que tenemos un algoritmo que espera una cantidad constante de tiempo cy luego imprime un mensaje de longitud N en tiempo lineal. (Esta es una generalización de la muestra de código original). Digamos arbitrariamente que esperamos veinte años para comenzar a imprimir, y que imprimir un billón de caracteres lleva otros veinte años. Sea c = 20 y k = 10¹², por ejemplo, pero cualquier número real positivo servirá. Esa es una tasa de d = c / k (en este caso 2 × 10⁻¹¹) años por carácter, por lo que nuestro tiempo de ejecución f ( N ) es asintóticamentedN + c años. Siempre que N > k , dN = c / k N > c . Por lo tanto, dN < dN + c = f ( N ) <2 dN para todo N > k , y f ( N ) ∈ Θ ( N ). QED

Creo que la gente se está volviendo loca porque el código no parece un algoritmo tradicional. Aquí hay una traducción del código que está mejor formada, pero se mantiene fiel al espíritu de la pregunta de OP.

void TrolloWorld(long currentUnixTime, long loopsPerMs){
    long laterUnixTime = 2051222400000;  //unix time of 01/01/2035, 00:00:00
    long numLoops = (laterUnixTime-currentUnixTime)*loopsPerMs;

    for (long i=0; i<numLoops; i++){
        print ("It's still not time to print the hello …");
    }
    print("Hello, World!");
}

Las entradas son explícitas, mientras que antes se daban implícitamente en el momento en que se iniciaba el código y por la velocidad del hardware que ejecuta el código. El código es determinista y tiene una salida bien definida para entradas dadas.

Debido a las limitaciones que se imponen a las entradas que podemos proporcionar, existe un límite superior para el número de operaciones que se ejecutarán, por lo que este algoritmo es de hecho O (1).

En este momento, sí

Este algoritmo tiene una entrada implícita, es decir, el momento en que se inicia el programa. El tiempo de ejecución variará linealmente ¹ dependiendo de cuándo se inicie. Durante el año 2035 y después, el ciclo while sale inmediatamente y el programa termina después de operaciones constantes ² . Entonces se podría decir que el tiempo de ejecución es O(max(2035 - start year, 1))³ . Pero dado que nuestro año de inicio tiene un valor mínimo, el algoritmo nunca tardará más de 20 años en ejecutarse (es decir, un valor constante).

Puede hacer que su algoritmo sea más acorde con su intención definiendo DateTime TwentyYearsLater = DateTime.Now + new TimeSpan(365*20,0,0,0);⁴

¹ Esto es válido para el sentido más técnico del tiempo de ejecución medido como número de operaciones porque hay un número máximo de operaciones por unidad de tiempo.
² Suponiendo que la búsqueda DateTime.Nowes una operación constante, lo cual es razonable.
³ Estoy abusando un poco de la notación O grande aquí porque esta es una función decreciente con respecto a start year, pero podríamos rectificarlo fácilmente expresándolo en términos de years prior to 2035.
⁴ Entonces, el algoritmo ya no depende de la entrada implícita de la hora de inicio, pero eso no tiene importancia.

Yo diría que esto es O (n). utilizando http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html como referencia.

¿Qué es Big O?

La notación Big O busca describir la complejidad relativa de un algoritmo al reducir la tasa de crecimiento a los factores clave cuando el factor clave tiende hacia el infinito.

y

El mejor ejemplo de Big-O que se me ocurre es hacer aritmética. Las operaciones aritméticas básicas que aprendimos en la escuela fueron:

adición; sustracción; multiplicación; y división. Cada uno de estos es una operación o un problema. Un método para resolverlos se llama algoritmo.

Por tu ejemplo,

dada la entrada de n = 20 (con unidades años).

el algoritmo es una función matemática f (). donde f () es esperar n años, con cadenas de 'depuración' en el medio. El factor de escala es 1. f () se puede reducir o aumentar cambiando este factor de escala.

para este caso, la salida también es 20 (al cambiar la entrada, la salida cambia linealmente).

esencialmente la función es

f(n) = n*1 = n
    if  n = 20, then 
f(20) = 20