I'm trying to follow a proof of an exercise from an algorithms textbook, and am confused about one the algebraic steps in the proof:
$lg(\theta(\frac{1}{n}))$ = $\theta(\frac{1}{n})$
Where $lg$ is $log_2$ (although base doesn't matter asymptotically). The full proof is at http://clrs.skanev.com/03/02/03.html
Wouldn't the asymptotic behavior of any $lg(f(x))$ function be different from just $f(x)$?
I should note that the proof is from a study group of the textbook and not from the textbook itself, so might be more likely to have mistakes.
The proof you linked to isn't very good. The whole issue could be avoided by noting that $\sqrt{2\pi n}(1 + \Theta(\frac1n)) = \Theta(\sqrt n)$ at the beginning.
The author's approach is still ok in principle, but they make a mistake when they replace $\log(\Theta(1)+\Theta(\frac1n))$ with $\Theta(\frac1n)$. The expression $\log(\Theta(1)+\Theta(\frac1n))$ is simply the logarithm of a bounded function, which could either be undefined or (if the function is bounded away from $0$) itself bounded, but not $\Theta(\frac1n)$ in general. It is true that the original $\log(1+\Theta(\frac1n))$ is legitimately $\Theta(\frac1n)$; this follows from the Taylor approximation to $\log(1+x)$ at $x=0$, as per qaphia's comment, and is probably what the author meant.
Note also that the author's "proof" that $n! = o(n^n)$ is incorrect: it shows that $n! \le n^n$, but that's not as strong as $o(n^n)$. (It's easy to modify the proof to get the additional information - just don't change the initial $1$ to an $n$, and get the upper bound $n^{n-1}$.)