Eu faço Análise de Sistemas na UFPR, e achei sua explicação excelente e muito fácil de utilizar.
Acrescentaria apenas que, como existem muitas linguagens de programação e cada uma implementa certas lógicas matemáticas de forma específica, é sempre interessante verificar a documentação da linguagem que se está utilizando para cada estrutura de dados, pois a depender da linguagem já tive surpresas quando realizei benchmarks!
Excelente ponto. Lembro que na faculdade usava muito C++ e na documentação das Estrutura de Dados sempre tinha uma seção de complexidade. Exemplo: https://cplusplus.com/reference/set/set/insert/ . Você vai ver que tem uma seção Complexidade que fala da complexidade do método insert do set. Em linguagens de alto nível como javascript isso já não é tão fácil de encontrar.
Eu geralmente tento inicialmente validar de forma intuitiva. É meio fácil de validar intuitivamente que métodos do array como find, some, filter vão iterar por todos os items do array no pior caso. Porém, concordo com você que outras estruturas vão ser mais complicadas e você provavelmente vai precisa pesquisar sobre, ver código fonte ou até mesmo fazer benchmarks.
Ótimo ponto!