Which of these two functions has a higher order of growth/complexity? Consider the following functions:
$$f(n)=2^{\log^*n} \text{ and } g(n)=\sqrt{2}^{\log{n}}$$
Using $\log{}$ properties I think that $g(n) &lt; f(n)$, since:

$f(n)\sim n$,
$g(n)\sim n^{\frac{1}{2}}$, and
$n^{\frac{1}{2}}&lt;n$.

However the book that I'm reading says otherwise.
What have I gotten wrong?
You have gotten wrong the 1st property, that $2^{\log^*(n)} \sim ~n$.  This is not the case.
The notation $\log^*(n)$ is the iterated logarithm, and the iterated logarithm grows much much slower than the logarithm, so $f$ grows much slower than linearly.