D'une part en informatique on est plus détendu qu'en maths sur la rigueur : en maths il faudrait une bijection strictement monotone, ici on se contente de quelque chose de vaguement monotone à partir d'un certain rang et définie sur les entiers, ça suffit bien! Et c'est bien le cas de toutes ces fonctions.

D'autre part en général on raisonne par équivalence, donc ce que l'on veut, c'est obtenir un équivalent de n solution de f(n)=t, c'est bien le problème d'inverser une bijection.

Pour 2^n c'est évident : n=ln_2(n).

Pour les deux autres il faut connaître quelques astuces sympa en analyse asymptotique :
n.ln(n)=t
on passe au log : ln(n)+ln(ln(n))=ln(t)
=> ln(n)~ln(t)
on reprend l'équation n.ln(n)=t : n.ln(t)~t
=> n~t/ln(t) Et hop le tour est joué.

Le dernier est un peu plus technique :
n!=t
mais n!~sqrt(2.pi.n).(n/e)^n
donc t~sqrt(2.pi.n).(n/e)^n
on passe au log comme la dernière fois et on fais un peu le ménage : ln(t)~n.ln(n)
et il ne reste qu'à appliquer une 2eme fois le passage au log pour obtenir ln(ln(t))~ln(n)
maintenant ln(t)~n.ln(ln(t)) donc n~ln(t)/ln(ln(t)) Et hop le tour est joué.

En gros le passage au log est souvent très utile en analyse asymptotique pour obtenir une information moins forte mais cachée par une formule qu'on arrive pas a exploiter.

Terrible! Merci pour cette méthode que je n'ai pas vu dans mes cours d'analyse.
Je pensais pas que ce problème serait aussi difficile.
Pour le 2^n, c'est vrai que j'aurais pu ne pas le poster.

Mais pour le n*lg(n).. ca aurait été un peu tendu sachant que j'ai pas encore vu ça.

Je comprends pas pourquoi ln(n)~ln(t), en asymptotique, c'est un équivalent quand n tend vers +infini, non?(t constant et ln(n)/ln(t) ne tend pas vers 1 quand n tend vers +infini?) Mais après comment j'exploite ma relation d'équivalence?

En considérant n~t/ln(t) (un équivalent pour n très grand.
(qd: n->+infini)).
Moins rigoureusement, on remplace par une égalité et puis basta?
Et pour faire plus rigoureusement, on fait comment?
Qu'est-ce qui nous permet de dire qu'un équivalent c'est une égalité à partir d'un certain rang?

Ensuite pour le dernier, c'est la formule de Stirling dont il s'agit, n'est-ce pas?  n!~sqrt(2.pi.n).(n/e)^n
Du coup, on re-exploite ta méthode.

t n'est pas constant, sinon on te le donnais et il te serais facile de retrouver n à la calculatrice :
si je te demande de me donner le plus grand n tq f(n)<3000, avec f:n->n.ln(n), tu n'aurais pas beaucoup de mal à me donner la réponse avec un petit arrondi.
Ici on introduit juste la variable t qui représente le temps maximal, et on veut le nombre n maximal traitable par la machine, en fonction de t. Il n'est pas possible (et totalement inutile) d'avoir quelque chose de très précis, un équivalent est suffisant pour avoir une idée de l'ordre de grandeur de ce qu'est capable de traiter notre machine. Ca ne deviens jamais une égalité, mais un informaticien qui regarde les capacités d'une machine n'en a rien à faire, du moment que l'équivalent a du sens. Déterminer à partir de quel rang l'équivalent est suffisamment précis (disons arbitrairement moins de 1% d'erreur) serait un autre exercice, et ce genre de vérification fait partie de l'analyse asymptotique.

Mais ne t'inquiète pas si tu ne comprends pas tout dès le début, il faut du temps pour se familiariser avec ces raisonnements. Le plus important c'est de ne jamais se laisser aller sur le plan de la rigueur et toujours savoir ce qu'on fait quand on utilise des notations abusives (comme dans mon post plus haut).

Sinon oui c'est la méthode de Stirling, d'ailleurs sa preuve est un bon exemple bien bourrin d'analyse asymptotique.

Je t'en remercie.

J'essaierai de creuser d'un peu plus près tout ça.