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!