De fato, Big-O é sobre o quão bem o desempenho escala conforme a quantidade de dados aumenta.
Mas só pra ser chato, mesmo assim vc cometeu um erro/vício que muitos de nós cometemos: colocou "tempo" nas definições. Só que Big-O não é sobre tempo. Ele é uma definição matemática que - e aqui vou ser bem teórico e genérico - descreve o comportamento assintótico (o "limite") de uma função quando o seu parâmetro se aproxima de determinado valor. Quando aplicado a algoritmos, ele dá uma ideia de como eles escalam conforme o tamanho dos dados aumenta (lembrando que ele é um limite superior, portanto considera o pior caso).
Outra definição encontrada aqui:
A ideia da notação Big-O é descrever o comportamento geral (também chamado de assintótico, pois é o comportamento no limite conforme os dados crescem) do algoritmo em termos do crescimento do número de operações conforme cresce o número de elementos processados (a quantidade de itens é descrita, genericamente, por
n).
Então o correto não é "tempo linear", "tempo constante", etc, e sim "complexidade linear", "complexidade constante" e por aí vai.
Mas dois algoritmos diferentes que são O(1), por exemplo, não necessariamente vão demorar o mesmo tempo (pode ser que no primeiro as instruções demorem mais, mas se todas sempre demoram o mesmo tempo, ainda será O(1)).
O mesmo algoritmo pode demorar mais em um hardware mais fraco.
Dois algoritmos O(n) não necessariamente são equivalentes, pois as constantes são desconsideradas: se um algoritmo percorre um array 2 vezes e outro percorre 5 vezes, ambos são O(n) - pois O(2n) e O(5n) são equivalentes do ponto de vista da definição matemática: a ideia é que, conforme N fica muito grande (quanto mais se aproxima do infinito), mais insignificante se tornam os fatores 2 e 5, e portanto eles são eliminados, ficando apenas o N.
E por aí vai, Big-O te dá uma informação importante sobre o algoritmo, mas não substitui um teste com dados reais no hardware final. Até porque, se forem poucos dados, aí as preocupações de escala se tornam menos relevantes. Afinal, para poucos dados, tudo é rápido.
O que o Big-O está contando de fato é a quantidade de "operações". Pegando um trecho deste link, em tradução livre:
Quando alguém diz que a complexidade de "tempo" do MergeSort é O(nlogn), na verdade eles querem dizer que o número de comparações que o MergeSort faz é O(nlogn). Isso por si só não diz muito sobre a complexidade de tempo que qualquer MergeSort em particular tenha, porque isso depende de quanto tempo demora para fazer uma comparação. Em outras palavras, O(nlogn) se refere a comparações como uma operação primitiva.
O importante aqui é que Big-O é aplicado a algoritmos, mas sempre há um modelo computacional por trás. Ao dizer que a complexidade de tempo do MergeSort é O(nlogn), implicitamente estamos referenciando um modelo computacional no qual o tempo da comparação é constante e todo o resto é "de graça".
Por exemplo, comparar dois números pode ser mais rápido que comparar duas strings, ou dois objetos complexos que exigem que vários campos sejam comparados (dois usuários, que devem ser ordenados por nome e idade), etc. O algoritmo de ordenação continua tendo a mesma complexidade (a mesma quantidade de comparações), mas o tempo vai variar de acordo com o que está sendo comparado.