I have been given the following questions and the answers shown in the picture below:enter image description here
I know how to find the order of a function without logs but when logs come into play, things get weird. For example in the first question I don't understand how is the order of growth ϴ(n^log5) and not ϴ(n^2). I checked this and n^2 always yields a larger result. Can someone please explain each?
For (i) the last term can be written as $n^{\lg5}$ where $\lg5=\lg_25>2$ (So here, I am assuming that $\lg$ is the log of base 2, which is likely the case here). This means that this term grows much faster. If $\lg$ refers to the natural log, then it is in fact $\Theta(n^2)$
For (ii) we rewrite the expression as $n\lg4+n+\lg{n}+n\lg{n}$. The $n\lg{n}$ term grows the fastest.
For (v) We rewrite the expression as $2\lg{n!}$. It can be shown that $\lg{n!}$ is actually $\Theta(n\lg{n})$