Há controvérsias. Isso pode ser visto nessa pergunta. Leia tudo, inclusive os comentários, tem coisa muito boa ali, inclusive mostrando como as coisas ocorrem de fato na prática.
Me parece que entende que medir a complexidade de algoritmo não é medir a velocidade dele. Há uma relação entre ambos, mas não é tão direta assim.
É claro que é impossível pegar muitos dados e ter um O(n^m) mais rápido que um O(1) em qualquer hardware.
O algoritmo, da maneira como as pessoas fazem, não leva em consideração condições de hardware.
O mais comum é classificar a eficiência dentro de um ambiente neutro. Em geral não considera-se otimizações.
Imagine rodar isso em um computador sobrecarregado. Toda teoria evapora. Imagina um computador que gasta mais tempo fazendo swap em disco do que no cálculo. De que adianta saber na teoria qual a eficiência do algoritmo?
Na teoria pode-se considerar o hardware. Pode-se adicionar variáveis que considere essas condições. Mas é muito raro ter vantagem em saber isso. Em geral isso é feito em ambiente acadêmico ou de análise muito específica e quando está se fazendo algo que terá muita utilização em algo que potencialmente precisa de muita performance. Então há casos para considerar todas variáveis. No dia a dia você faz uma análise de eficiência superficial para escolher o algoritmo correto e faz testes reais de velocidade com dados típicos e extremos para ver o que acontece de fato em condições reais. Costuma dar resultados mais adequados do ponto de vista de engenharia, ainda que do ponto de vista científico não seja necessariamente o melhor.
Eu já vi gente dizendo que existem cálculos nesse sentido, mas nunca vi alguém os mostrando. Eu sei que eles existem, mas estão bem escondidos :)
Dito tudo isso, a minha experiência mostra que cache faz mais diferença do que branch prediction na maioria dos casos. Algoritmos que possuem menos branches podem ser mais eficientes em máquinas mais simples.
Um algoritmo que deve manipular dados em disco pode ser o mais adequado, enquanto que os mesmo dados em memória outro algoritmo pode ser mais adequado. Imagine que um cache L1 ou até mesmo registradores pudessem comportar todos os dados a serem processados como poderia haver melhoria.
Lembrando que para poucos dados (N baixo), na prática, tanto faz qual o algoritmo usado.
Veja isto Algoritmos de ordenação de memória externa e interna.