Récursivité et complexité

Reprendre et terminer les exercices des td précédents en donnant leur complexité en temps et en place.

On suppose qu'un ordinateur effectuant 10 milliard d'instructions élémentaires par seconde fonctionne depuis 10 milliards d'années.

• Combien d'instructions élémentaires a-t-il effectué pendant cette période ?
• Déterminer le nombre de déplacement nécessaire pour résoudre le problème des tours de Hanoï avec n disques.
• En supposant que le déplacement d'un plateau soit une instruction élémentaire, quelle valeur de n peut traiter l'ordinateur précédent en 10 milliards d'années ?