Provavelmente, o problema com o comando locate é que o banco de dados ainda não foi atualizado para refletir os arquivos do pacote recém-instalado. Você poderia forçar uma atualização ( sudo updatedb ) ou usar o comando find , mas provavelmente a solução mais fácil em sistemas como o Ubuntu que usam as ferramentas de gerenciamento de pacotes dpkg é listar o conteúdo do pacote
dpkg -L libgoogle-perftools-dev
ou para verificar a localização do arquivo profiler.h especificamente
dpkg -L libgoogle-perftools-dev | grep 'profiler.h'