Tem outro vídeo do Bjarne que aparece o gráfico que ele cita. Além do material dele, tem vários outros de CppCon, CppOnSea, CppNow... em resumo, a maioria dos algoritmos e estrutura de dados hoje em dia é um grande "depende", porque as constantes importam tanto ou mais que Big-O.

sem contar que big O não diz se um algoritmo é lento ou rápido, só, bem basicamente, como ele se comporta quando a massa de dados cresce tu pode ter um algoritmo que leva 1s pra rodar com complexidade O(logN) e ter um que leva 100ms O(N), qual tu escolheria? como diz o papagaio sênior, depende