Isso seria classificado como um algoritmo O (1) para "Hello, World!" ??

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!");
   }
}

Estou pensando em usar o

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

trecho de código como um loop ocupado para colocar como uma piada sempre que alguém pede um algoritmo de certa complexidade. Isso seria correto?

A notação Big O neste contexto está sendo usada para descrever uma relação entre o tamanho da entrada de uma função e o número de operações que precisam ser realizadas para calcular o resultado dessa entrada.

Sua operação não tem entrada à qual a saída possa ser relacionada, portanto, usar a notação Big O é absurdo. O tempo que a operação leva é independente das entradas da operação (que é ... nenhum). Uma vez que não é nenhuma relação entre a entrada e o número de operações realizadas, você não pode usar Big O para descrever essa relação inexistente

A notação Big-O significa aproximadamente 'dada uma operação em uma quantidade de trabalho, N, quanto tempo de cálculo, proporcional a N, o algoritmo leva?' Por exemplo, classificar uma matriz de tamanho N pode levar N ^ 2, Nlog (N), etc.

Não há quantidade de dados de entrada para agir. Então não é O(anything).

Pior ainda; isso não é tecnicamente um algoritmo. Um algoritmo é um método para calcular o valor de uma função matemática - funções matemáticas são um mapeamento de uma entrada para uma saída. Uma vez que isso não leva entrada e não retorna nada, não é uma função, no sentido matemático. Da wikipedia:

Um algoritmo é um método eficaz que pode ser expresso em uma quantidade finita de espaço e tempo e em uma linguagem formal bem definida para o cálculo de uma função. Começando de um estado inicial e entrada inicial (talvez vazio), as instruções descrevem um cálculo que, quando executado, prossegue através de um número finito de estados sucessivos bem definidos, eventualmente produzindo "saída" e terminando em um estado final final.

O que isso é, tecnicamente, é um sistema de controle. Da wikipedia;

Um sistema de controle é um dispositivo, ou conjunto de dispositivos, que gerencia, comanda, dirige ou regula o comportamento de outros dispositivos ou sistemas.

Para as pessoas que desejam uma resposta mais aprofundada sobre a diferença entre funções matemáticas e algoritmos, e as habilidades mais poderosas dos computadores para fazer coisas de efeito colateral, como saída de console, exibição de gráficos ou controle de robôs, leia este artigo sobre o Hipótese forte de Church-Turing

Resumo

A visão clássica da computação posiciona o cálculo como uma transformação de caixa fechada de entradas (números racionais ou strings finitas) em saídas. De acordo com a visão interativa da computação, a computação é um processo interativo contínuo, em vez de uma transformação baseada em função de uma entrada em uma saída. Especificamente, a comunicação com o mundo externo acontece durante a computação, não antes ou depois dela. Essa abordagem muda radicalmente nossa compreensão do que é computação e como ela é modelada.

A aceitação da interação como um novo paradigma é dificultada pela Strong Church-Turing Thesis (SCT), a crença generalizada de que as máquinas de Turing (TMs) capturam toda a computação, portanto, modelos de computação mais expressivos do que TMs são impossíveis. Neste artigo, mostramos que a SCT reinterpreta a Tese de Church-Turing (CTT) original de uma maneira que Turing nunca pretendeu; sua equivalência comumente assumida com o original é um mito. Identificamos e analisamos as razões históricas para a crença generalizada na SCT. Somente aceitando que é falso podemos começar a adotar a interação como um paradigma alternativo de computação

Não, seu código tem complexidade de tempo de O(2^|<DeltaTime>|),

Para uma codificação adequada da hora atual.
Por favor, deixe-me primeiro pedir desculpas pelo meu inglês.

O que é e como o Big O funciona no CS

A notação Big O não é usada para amarrar a entrada de um programa com seu tempo de execução .
A notação Big O é, deixando para trás o rigor, uma forma de expressar a proporção assintótica de duas quantidades .

No caso da análise de algoritmo, essas duas grandezas não são a entrada (para a qual é necessário primeiro ter uma função de "medida") e o tempo de execução.
Eles são o comprimento da codificação de uma instância do problema ¹ e uma métrica de interesse.

As métricas comumente usadas são

1. O número de etapas necessárias para concluir o algoritmo em um determinado modelo de computação.
2. O espaço necessário, se tal conceito existir, pelo modelo de computação.

Implicitamente é assumido um TM como o modelo de forma que o primeiro ponto se traduz no número de aplicações da função de transição ² , ou seja, "etapas", e o segundo ponto traduz o número de células de fita diferentes escritas pelo menos uma vez .

Também é frequentemente assumido implicitamente que podemos usar uma codificação relacionada polinomialmente em vez da original, por exemplo, uma função que pesquisa uma matriz do início ao fim tem O(n)complexidade, apesar do fato de que uma codificação de uma instância de tal matriz deve ter comprimento de n*b+(n-1)onde bé o número (constante) de símbolos de cada elemento. Isso ocorre porque bé considerada uma constante do modelo de cálculo e, portanto, as expressões acima e nsão assintoticamente iguais.

Isso também explica por que um algoritmo como a Divisão de Teste é um algoritmo exponencial , apesar de ser essencialmente um for(i=2; i<=sqr(N); i++)algoritmo semelhante ³ .

Veja isso .

Isso também significa que a notação grande O pode usar quantos parâmetros forem necessários para descrever o problema, não é incomum ter um parâmetro k para alguns algoritmos.

Portanto, não se trata de "entrada" ou de "não há entrada".

Estudo de caso agora

A notação Big O não questiona seu algoritmo, apenas assume que você sabe o que está fazendo. É essencialmente uma ferramenta aplicável em qualquer lugar, até mesmo para algoritmos que podem ser deliberadamente complicados (como o seu).

Para resolver o seu problema você usou a data atual e uma data futura, então elas devem fazer parte do problema de alguma forma; Simplificando: eles são parte da instância do problema.

Especificamente, a instância é:

<DeltaTime>

Onde o <>significa qualquer codificação não patológica de escolha.

Veja abaixo esclarecimentos muito importantes .

Portanto, o seu grande tempo de complexidade O é justo O(2^|<DeltaTime>|)porque você faz uma série de iterações que dependem do valor do tempo atual. Não há sentido em colocar outras constantes numéricas, pois a notação assintótica é útil, pois elimina constantes (então, por exemplo, o uso de O(10^|<DeltaTime>|*any_time_unit)é inútil).

Onde está a parte complicada

Fizemos uma suposição importante acima: que o modelo de computação reafirma ⁵ tempo, e por tempo quero dizer o tempo físico (real?). Não existe tal conceito no modelo computacional padrão, uma TM não conhece o tempo, relacionamos o tempo com o número de passos porque é assim que a nossa realidade funciona ⁴ .

No seu modelo, no entanto, o tempo faz parte do cálculo, você pode usar a terminologia de pessoas funcionais dizendo que Main não é puro, mas o conceito é o mesmo.

Para entender isso deve-se observar que nada impede o Framework de usar um tempo falso que roda duas, cinco, dez vezes mais rápido que o tempo físico. Desta forma, seu código será executado na "metade", "um quinto", "um décimo" do "tempo".

Esta reflexão é importante para escolher a codificação de <DeltaTime>, esta é essencialmente uma forma condensada de escrever <(CurrentTime, TimeInFuture)>. Visto que o tempo não existe a priory, a codificação de CurrentTime poderia muito bem ser a palavra Now (ou qualquer outra escolha) no dia anterior poderia ser codificada como Yesterday , quebrando a suposição de que o comprimento do aumento de codificação conforme o tempo físico avança (e o de DeltaTime diminui)

Temos que modelar corretamente o tempo em nosso modelo computacional para fazer algo útil.

A única escolha segura que podemos fazer é codificar timestamps com comprimentos crescentes (mas ainda sem usar unário) conforme o tempo físico avança. Esta é a única propriedade verdadeira do tempo de que precisamos e que a codificação precisa capturar. É apenas com esse tipo de codificação que seu algoritmo pode ter uma complexidade de tempo.

Sua confusão, se houver, surge do fato de que a palavra tempo nas frases 'Qual é sua complexidade de tempo ?' e 'Quanto tempo vai demorar?' significa coisas muito diferentes

Infelizmente, a terminologia usa as mesmas palavras, mas você pode tentar usar "etapas complexas" em sua cabeça e fazer novamente a si mesmo sua pergunta, espero que isso o ajude a entender que a resposta é realmente ^ _ ^

¹ Isso também explica a necessidade de uma abordagem assintótica, pois cada instância tem um comprimento diferente, embora não arbitrário.
² Espero estar usando o termo inglês correto aqui.
³ Também é por isso que frequentemente encontramos log(log(n))termos na matemática.
⁴ Id est, uma etapa deve ocupar algum intervalo de tempo finito, mas não nulo, nem conectado.
⁵ Isso significa que o modo computacional como um conhecimento do tempo físico nele, ou seja, pode expressá-lo com seus termos. Uma analogia é como os genéricos funcionam na estrutura .NET.

Embora haja um monte de ótimas respostas aqui, deixe-me reformular todas elas um pouco.

A notação Big-O existe para descrever funções . Quando aplicado à análise de algoritmos, isso exige que primeiro definamos algumas características desse algoritmo em termos de uma função . A escolha comum é considerar o número de etapas em função do tamanho da entrada . Como observado em outras respostas, sugerir tal função no seu caso parece estranho, porque não há uma "entrada" claramente definida. Ainda podemos tentar fazer isso:

• Podemos considerar seu algoritmo como uma função constante que pega qualquer entrada de qualquer tamanho, a ignora, espera um período fixo de tempo e termina. Nesse caso, seu tempo de execução é f (n) = const e é um algoritmo de tempo O (1). Era isso que você esperava ouvir, certo? Sim, é, tecnicamente, um O (1) -algoritmo .
• Podemos considerar o TwentyYearsLatercomo o parâmetro de interesse do tipo "tamanho de entrada". Neste caso, o tempo de execução é f (n) = (nx) onde x é o "agora" no momento da invocação. Quando visto desta forma, é um algoritmo de tempo O (n). Espere esse contra-argumento sempre que for mostrar seu algoritmo O (1) -técnico para outras pessoas.
• Oh, mas espere, se k =TwentyYearsLater é a entrada, então seu tamanho n é, na verdade, o número de bits necessários para representá-la, ou seja, n = log (k) . A dependência entre o tamanho da entrada n e o tempo de execução é, portanto, f (n) = 2 ^ n - x . Parece que seu algoritmo acabou de ficar exponencialmente lento! Ugh.
• Outra entrada para o programa é, de fato, o fluxo de respostas fornecidas pelo sistema operacional para a sequência de DateTime.Nowinvocações no loop. Na verdade, podemos imaginar que toda essa sequência é fornecida como entrada no momento em que executamos o programa. O tempo de execução pode então ser considerado como dependente da propriedade dessa sequência - ou seja, seu comprimento até o primeiro TwentyYearsLaterelemento. Nesse caso, o tempo de execução é novamente f (n) = n e o algoritmo é O (n) .

Mas, novamente, em sua pergunta você nem mesmo disse que estava interessado em runtime. E se você quisesse dizer uso de memória? Dependendo de como você modela a situação, você pode dizer que o algoritmo é O (1) -memória ou, talvez, O (n) -memória (se a implementação de DateTime.Nowexigir o controle de toda a sequência de invocação de alguma forma).

E se o seu objetivo era inventar algo absurdo, por que você não vai all in e diz que está interessado em como o tamanho do código do algoritmo em pixels na tela depende do nível de zoom escolhido. Isso pode ser algo como f (zoom) = 1 / zoom e você pode orgulhosamente declarar que seu algoritmo tem tamanho de O (1 / n) pixel!

Tenho que discordar ligeiramente de Servy. Existe uma entrada para este programa, mesmo que não seja óbvia, e essa é a hora do sistema. Isso pode ser um detalhe técnico que você não pretendia, mas sua TwentyYearsFromNowvariável não é vinte anos do tempo do sistema agora , ela é atribuída estaticamente a 1º de janeiro de 2035.

Portanto, se você pegar este código e executá-lo em uma máquina que tem um horário de sistema de 1º de janeiro de 1970, levará 65 anos para ser concluído, independentemente da velocidade do computador (pode haver alguma variação se o relógio estiver com defeito ) Se você pegar esse código e executá-lo em uma máquina com hora do sistema de 2 de janeiro de 2035, ele será concluído quase que instantaneamente.

Eu diria que sua entrada, né January 1st, 2035 - DateTime.Now, e é O (n).

Depois, há também a questão do número de operações. Algumas pessoas notaram que computadores mais rápidos entrarão no loop com mais rapidez, causando mais operações, mas isso é irrelevante. Ao trabalhar com a notação big-O, não consideramos a velocidade do processador ou o número exato de operações. Se você pegasse esse algoritmo e o executasse em um computador e, em seguida, o executasse novamente, mas por mais 10 vezes no mesmo computador, esperaria que o número de operações crescesse pelo mesmo fator de 10 vezes.

Quanto a isso:

Estou pensando em usar o trecho de código [código redigido] como um loop ocupado para colocar como uma piada sempre que alguém pede um algoritmo de certa complexidade. Isso seria correto?

Não, na verdade não. Outras respostas cobriram isso, então eu só queria mencioná-lo. Você geralmente não pode correlacionar anos de execução a qualquer notação big-O. Por exemplo. Não há como dizer 20 anos de execução = O (n ^ 87) ou qualquer outra coisa nesse sentido. Mesmo no algoritmo que você forneceu, eu poderia mudar o TwentyYearsFromNowpara o ano 20110, 75699436 ou 123456789 e o big-O ainda é O (n).

A análise Big-O lida com a quantidade de processamento envolvida conforme a quantidade de dados sendo processados ​​aumenta sem limite.

Aqui, você está realmente lidando com um único objeto de tamanho fixo. Como tal, a aplicação da análise big-O depende muito (principalmente?) De como você define seus termos.

Por exemplo, você pode significar impressão de saída em geral e impor uma espera tão longa que qualquer quantidade razoável de dados seria / será impressa precisamente no mesmo período de tempo. Você também tem que adicionar um pouco mais na forma de definições um tanto incomuns (se não totalmente erradas) para ir muito longe - particularmente, a análise big-O é geralmente definida em termos do número de operações fundamentais necessárias para realizar um tarefa específica (mas observe que a complexidade também pode ser considerada em termos de coisas como uso de memória, não apenas uso de CPU / operações realizadas).

O número de operações fundamentais geralmente se traduz de forma bastante próxima ao tempo gasto, no entanto, não é um exagero tratar os dois como sinônimos. Infelizmente, no entanto, ainda estamos presos a essa outra parte: a quantidade de dados sendo processados ​​aumentando sem limite. Sendo esse o caso, nenhum atraso fixo que você possa impor realmente funcionará. Para igualar O (1) com O (N), você teria que impor um atraso infinito para que qualquer quantidade fixa de dados demorasse uma eternidade para ser impressa, assim como faria uma quantidade infinita de dados.

big-O em relação a quê?

Você parece estar intuindo que twentyYearsLateré uma "entrada". Se você realmente escreveu sua função como

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

Seria O (N) onde N = anos (ou apenas diga O(years)).

Eu diria que seu algoritmo é O (N) em relação a qualquer número que você escreva na linha de código que começa twentyYearsLater =. Mas as pessoas geralmente não consideram os números no código-fonte real como entrada. Eles podem considerar a entrada da linha de comando como a entrada ou a entrada da assinatura da função como a entrada, mas muito provavelmente não o código-fonte em si. É isso que você está disputando com seu amigo - é essa a "entrada"? Você configura seu código de forma a fazê-lo intuitivamente parecer uma entrada, e você pode definitivamente perguntar seu grande tempo de execução O em relação ao número N na linha 6 do seu programa, mas se você usar essa escolha não padrão como entrada, você realmente precisa ser explícito sobre isso.

Mas se você considerar a entrada como algo mais usual, como a linha de comando ou a entrada para a função, não há saída nenhuma e a função é O (1). Leva vinte anos, mas como big-O não muda até um múltiplo constante, O (1) = O (vinte anos).

Pergunta semelhante - qual é o tempo de execução de:

void sortArrayOfSizeTenMillion(int[] array)

Supondo que ele faça o que diz e a entrada seja válida, e o algoritmo aproveite um quicksort ou tipo de bolha ou qualquer coisa razoável, é O (1).

Este "algoritmo" é corretamente descrito como O (1) ou tempo constante. Foi argumentado que não há entrada para este programa, portanto, não há N para analisar em termos de Big Oh. Não concordo que não haja entrada. Quando ele é compilado em um executável e chamado, o usuário pode especificar qualquer entrada de comprimento arbitrário. Esse comprimento de entrada é o N.

O programa apenas ignora a entrada (de qualquer comprimento), então o tempo gasto (ou o número de instruções de máquina executadas) é o mesmo, independentemente do comprimento da entrada (dado ambiente fixo = hora de início + hardware), portanto, O (1 )

Uma coisa que me surpreende ainda não foi mencionada: a notação big-O é um limite superior!

O problema que todos notaram é que não há N descrevendo as entradas para o algoritmo, portanto, não há nada para fazer a análise big-O. No entanto, isso é facilmente atenuado com alguns truques básicos, como aceitar um int ne imprimir nhorários "Hello World" . Isso contornaria essa reclamação e voltaria à verdadeira questão de como essa DateTimemonstruosidade funciona.

Não há garantia real de que o loop while acabará. Gostamos de pensar que precisa em algum momento, mas considere que DateTime.nowretorna a data e hora do sistema . Na verdade, não há garantia de que isso esteja aumentando monotonicamente. É possível que haja algum macaco patologicamente treinado mudando constantemente a data e a hora do sistema para 21 de outubro de 2015 12:00:00 UTC até que alguém dê ao macaco alguns sapatos de ajuste automático e uma prancha. Na verdade, esse loop pode ser executado por um período infinito de tempo!

Quando você realmente se aprofunda na definição matemática das notações big-O, eles são os limites superiores. Eles demonstram o pior cenário, não importa o quão improvável seja. O pior caso * cenário aqui é um tempo de execução infinito, então somos forçados a declarar que não há nenhuma notação big-O para descrever a complexidade do tempo de execução desse algoritmo. Ele não existe, assim como 1/0 não existe.

* Edit: de minha discussão com KT, nem sempre é válido presumir que o cenário que estamos modelando com a notação big-O é o pior caso. Na maioria dos casos, se um indivíduo falha em especificar qual caso estamos usando, eles pretendem explorar o pior caso. No entanto, você pode fazer uma análise de complexidade big-O no melhor caso de tempo de execução.

A complexidade é usada para medir a "potência" computacional em termos de tempo / espaço. A notação Big O é usada para comparar quais problemas são "computáveis" ou "não computáveis" e também para comparar quais soluções -algoritmos- são melhores que outras. Assim, você pode dividir qualquer algoritmo em duas categorias: aqueles que podem ser resolvidos em tempo polinomial e aqueles que não podem.

Problemas como a peneira de erathostene são O (n ^ exp) e, portanto, podem ser resolvidos para pequenos valores de n. Eles são computáveis, mas não em tempo polinomial (NP) e, portanto, quando perguntado se um determinado número é primo ou não, a resposta depende da magnitude desse número. Além disso, a complexidade não depende do hardware, então ter computadores mais rápidos não muda nada ...

Hello World não é um algoritmo e, como tal, não faz sentido tentar determinar sua complexidade - que é nenhuma. Um algoritmo simples pode ser algo como: dado um número aleatório, determine se ele é par ou ímpar. Agora, faz diferença que o número fornecido tenha 500 dígitos? Não, porque você só precisa verificar se o último dígito é par ou ímpar. Um algoritmo mais complexo seria determinar se um determinado número se divide uniformemente por 3. Embora alguns números sejam "fáceis" de calcular, outros são "difíceis" e isso se deve à sua magnitude: compare o tempo que leva para determinar o remanescente entre um número com um dígito e outro com 500 dígitos.

Um caso mais complexo seria decodificar um texto. Você tem uma aparente matriz aleatória de símbolos que também sabe que transmitem uma mensagem para aqueles que têm a chave de descriptografia. Digamos que o remetente usou a chave à esquerda e seu Hello World leria: Gwkki Qieks. A solução "big-hammer, no-brain" produziria todas as combinações para essas letras: de Aaaa a Zzzz e, em seguida, pesquisar um dicionário de palavras para identificar quais palavras são válidas e compartilhar as duas letras comuns na cifra (i, k) em a mesma posição. Essa função de transformação é o que o Big O mede!

A maioria das pessoas parece estar perdendo duas coisas muito importantes.

1. O programa faz ter uma entrada. É a data / hora codificada com a qual a hora do sistema está sendo comparada. As entradas estão sob o controle da pessoa que executa o algoritmo, e a hora do sistema não. A única coisa que a pessoa que está executando este programa pode controlar é a data / hora em que codificou para a comparação.

2. O programa varia com base no valor de entrada , mas não no tamanho do conjunto de entrada , que é o motivo da notação big-O.

Portanto, é indeterminado e a melhor notação 'big-O' para este programa provavelmente seria O (nulo), ou possivelmente O (NaN).

Todo mundo corretamente apontou que você não define N , mas a resposta é não na interpretação mais razoável. Se N for o comprimento da string que estamos imprimindo e "olá, mundo!" é apenas um exemplo, como podemos inferir da descrição disso como um algoritmo "para" hello, world!, então o algoritmo é O ( N ), porque você pode ter uma string de saída que leva trinta, quarenta ou cinquenta anos para ser impressa, e você estamos adicionando apenas um tempo constante a isso. O ( kN + c ) ∈ O ( N ).

Termo aditivo:

Para minha surpresa, alguém está contestando isso. Lembre-se das definições de grande O e grande Θ. Suponha que temos um algoritmo que espera por uma quantidade constante de tempo c e então imprime uma mensagem de comprimento N em tempo linear. (Esta é uma generalização do exemplo de código original.) Digamos arbitrariamente que esperamos vinte anos para começar a imprimir e que imprimir um trilhão de caracteres leva outros vinte anos. Sejam c = 20 ek = 10¹², por exemplo, mas qualquer número real positivo serve. Essa é uma taxa de d = c / k (neste caso 2 × 10⁻¹¹) anos por caractere, então nosso tempo de execução f ( N ) é assintoticamentedN + canos. Sempre que N > k , dN = c / k N > c . Portanto, dN < dN + c = f ( N ) <2 dN para todos N > k , e f ( N ) ∈ Θ ( N ). QED

Acho que as pessoas estão ficando confusas porque o código não se parece com um algoritmo tradicional. Aqui está uma tradução do código que é mais bem formado, mas permanece fiel ao espírito da pergunta do 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!");
}

As entradas são explícitas, ao passo que antes eram fornecidas implicitamente no momento em que o código foi iniciado e pela velocidade do hardware que o executava. O código é determinístico e tem uma saída bem definida para as entradas fornecidas.

Por causa das limitações que são impostas às entradas que podemos fornecer, há um limite superior para o número de operações que serão executadas, portanto, esse algoritmo é na verdade O (1).

Neste momento, sim

Este algoritmo tem uma entrada implícita, ou seja, a hora em que o programa é iniciado. O tempo de execução irá variar linearmente ¹ dependendo de quando é iniciado. Durante o ano de 2035 e após, o loop while sai imediatamente e o programa termina após operações constantes ² . Portanto, pode-se dizer que o tempo de execução é O(max(2035 - start year, 1))³ . Mas, como nosso ano de início tem um valor mínimo, o algoritmo nunca levará mais de 20 anos para ser executado (ou seja, um valor constante).

Você pode tornar seu algoritmo mais compatível com sua intenção definindo DateTime TwentyYearsLater = DateTime.Now + new TimeSpan(365*20,0,0,0);⁴

¹ Isso é válido para o sentido mais técnico de tempo de execução medido como número de operações porque há um número máximo de operações por unidade de tempo.
² Presumindo que a busca DateTime.Nowseja uma operação constante, o que é razoável.
³ Estou abusando de alguma forma da grande notação O aqui porque esta é uma função decrescente em relação a start year, mas poderíamos facilmente retificar isso expressando-a em termos de years prior to 2035.
⁴ Então, o algoritmo não depende mais da entrada implícita da hora de início, mas isso não tem consequências.

Eu diria que este é O (n). usando http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html como referência.

O que é Big O?

A notação Big O procura descrever a complexidade relativa de um algoritmo, reduzindo a taxa de crescimento aos fatores-chave quando o fator-chave tende para o infinito.

e

O melhor exemplo de Big-O em que posso pensar é fazer aritmética. As operações aritméticas básicas que aprendemos na escola foram:

Adição; subtração; multiplicação; e divisão. Cada um deles é uma operação ou um problema. Um método para resolver isso é chamado de algoritmo.

Para o seu exemplo,

dada a entrada de n = 20 (com unidades anos).

o algoritmo é uma função matemática f (). onde f () passa a ser wait por n anos, com strings de 'depuração' entre eles. O fator de escala é 1. f () pode ser reduzido / ou aumentado alterando este fator de escala.

para este caso, a saída também é 20 (mudar a entrada muda a saída linearmente).

essencialmente, a função é

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