Só um detalhe, que é uma confusão que muitos fazem: complexidade não mede o tempo de execução. O único jeito de saber o tempo exato que um programa leva para executar é testando-o em condições reais.
O que funções como o Big-O fazem é determinar o "trabalho" necessário para executar o algoritmo. Na verdade, para ser mais exato, o Big-O determina o quanto esse "trabalho" aumenta conforme os dados de entrada crescem e se aproximam do infinito. É um conceito matemático bem abstrato que foi adaptado para a computação (inclusive, a definição matemática é muito mais ampla e genérica).
Como dito aqui:
Big O is not used for comparing run times, but for comparing how those run times scale as the input size grows.
Ou seja, Big-O não é usado para comparar o tempo de execução, mas sim para comparar como esses tempos aumentam conforme o tamanho da entrada cresce. Ele não diz se o algoritmo é mais rápido que outro. Ele só diz como essa "velocidade" muda quando o tamanho do problema aumenta.
Se eu digo que um algoritmo é O(n) e outro é O(n2), quer dizer que a quantidade de operações (de "trabalho executado") do primeiro aumenta em uma escala menor se comparado ao segundo, conforme o "n" (o tamanho da entrada, ou a quantidade de dados que serão processados) aumenta.
Mas isso não diz nada sobre o tempo que eles levam para executar. Por exemplo, se o primeiro faz operações mais demoradas (como escrever em arquivos) e o segundo só faz cálculos simples, pode ser que o primeiro seja até mais lento, mesmo executando menos operações. De novo: o tempo de execução só pode ser medido testando o código em condições reais, e não é isso que a complexidade de algoritmos mede. Inclusive, podemos até ter dois algoritmos O(n) que levam tempos completamente diferentes para executar.
Por fim, podemos usar a complexidade para medir diferentes aspectos, os mais comuns são tempo e espaço. Por exemplo, um algoritmo pode ser O(logn) em termos de "tempo" (lembrando que não quer dizer que mede o tempo, e sim como ele aumenta conforme o tamanho da entrada cresce) e O(n2) em termos de espaço (o algoritmo pode exigir a alocação de estruturas auxiliares que ocupam um espaço quadrático em relação à entrada, gastando mais memória).
Ou seja, complexidade é uma ferramenta para analisar algoritmos, e pode ser usado como um fator de decisão para escolha e avaliação. Vc pode ter uma ideia do tempo, ou se haverá memória suficiente, e já descartar os piores, por exemplo. Mas não dispensa o teste em condições reais, que no fim é o que vale. Afinal, funções como o Big-O são assintóticas, o que quer dizer que estão interessadas no comportamento "de longo prazo" (quando a entrada se aproxima do infinito). E como na prática não lidamos com dados infinitos, sempre precisa testar com dados reais. Inclusive, pode ter casos em que tanto faz, pois para poucos dados, tudo é rápido.
Para saber mais: