Não conhecia o gprof, achei interessante e aqui vai a dica.

O gprof é um programa do projeto GNU que mede os tempos de execução dos métodos presentes em um programa, possibilitando ao programador a análise desses tempos e a conseqüente otimização de seu código.

Para utilizá-lo siga os seguintes passos:

1. Compile o programa com a opção "-p":
   
   gcc -p -o "nome_do_seu_programa" "nome_do_arquivo.c"
   
   
2. Execute o seu programa normalmente. Será criado um arquivo com o nome gmon.out no diretório onde está o programa.
   
   
3. Execute o gprof:
   
   gprof --brief -p "nome_do_seu_programa"
   
   

OK, agora você pode conferir os tempos de execução dos métodos do seu programa.

OBS: Experimente tirar a opção "--brief" da chamada para o gprof.