How can I prove that eventually one function will overtake another, and find when? Given for example 2 functions,$\ n^{100} $ and$\ 2^n$. I know that$\ 2^n$ grows faster and that therefore there is some$\ n$ where it will eventually overtake $\ n^{100} $ but how can I prove this, and also maybe find that$\ n$?

Solve $2^n > n^{100} \iff n\ln 2>100\ln n\iff \dfrac{n}{\ln n} > \dfrac{100}{\ln 2}$. Let $n = 2^k$, then $ \dfrac{n}{\ln n} = \dfrac{2^k}{k}$,and you solve $2^k > 100k$. Observe the first integer solution $k$ for this is $k = 10$. Thus $n = 2^{10} = 1,024$ .
