  We study theoretically and experimentally the dependence of the
electron-phonon interaction in Na$_x$CoO$_2$ on the sodium concentration $x$.
For the two oxygen phonon modes found in Raman experiments, $A_{1g}$ and
$E_{1g}$, we calculate the matrix elements of the electron-phonon interaction.
Analyzing the feedback effect of the conduction electrons on the phonon
frequency we compare the calculated and experimentally observed doping
dependence of the $A_{1g}$ mode. Furthermore, due to the momentum dependence of
the electron-phonon coupling for the $E_{1g}$ symmetry we find no
renormalization of the corresponding phonon frequency which agrees with
experiment. Our results shed light on the possible importance of the
electron-phonon interaction in this system.
