What is the behavior of these functions linear or logarithmic or neither?

Question

Please consider the following functions $F$ and $G$. \begin{align*} F(K) = \log_2 \left(\frac{( 2\sqrt{K-1}+K-2)^2}{(\sqrt{K-1}-1)^2}\right)+(K-1) \log_2(2) \end{align*} and the function \begin{align*} G(K)= \log \left( \bigg( \frac{K^2-2}{(K-1)^2}\bigg) \ \frac{(2\sqrt{K-1}+K-2)^2}{(\sqrt{K-1}-1)^2} \right) +(K-2)\log_{2}\left(\frac{(K^2-2)}{2(K-1)^2} \frac{(\sqrt{K-1}+1)^2}{(\sqrt{K-1}-1)^2}\right) +(K-2)\log(2) \end{align*}

I should note that $K$ is a positive integer greater than 2.

My question is I don't really understand how these functions are behaving a a function of $K$? Are these functions linear or logarithmic as function of $K$ or something else...

Any help would be much appreciated.

Answer 1

My first reaction to questions like this is "By what hideous process did you come up with these things?"

My second is to run some quick intuition on them.

For F, I notice that nothing inside the first term is exponential, so it is at best the log of a polynomial-ish function in K, whereas the second term is linear in K. The log of a polynomial behaves like the log of K (because $\log{K^n}=n\log{K}$), and log is slower than linear, so F will be asymptotically dominated by the linear term for large K.

For G, the first and third terms follow the same logic, but at first glance it's hard to say what the middle term will be like. It's a product of being linear in K and something involving logs, so the question is what the bit inside the log is like. It looks like the numerator is a $K^2$-like term times a $K$-like term (because when you expand the second bit out you'll get $K+1+\sqrt{stuff}+1$), so it's roughly $K^3$, and it looks like the denominator is too, so they're going to cancel out and actually I think we'll have to work a little harder to figure out what it's doing but my uninformed guess is that it won't matter and the whole thing is still basically linear in K.

Note that these are all asymptotic behaviours for large K. Neither function is actually linear or logarithmic. And if you actually want asymptotic behaviour for, e.g., $K\rightarrow 0$, then I think the logarithmic terms are likely to dominate over the linear ones.

That said, let's get a bit more formal.

$\begin{eqnarray} F(K) &=& \log_2 \left(\frac{( 2\sqrt{K-1}+K-2)^2}{(\sqrt{K-1}-1)^2}\right)+(K-1) \log_2(2) \\ &=& \log{(2\sqrt{K-1}+K-2)^2}-\log{(\sqrt{K-1}-1)^2}+(K-1) \\ &=& 2\log{(K+2\sqrt{K-1}-2)}-\log{(K-1-2\sqrt{K-1}+1)}+(K-1) \\ &=& 2\log{(K+2\sqrt{K-1}-2)}-\log{(K-2\sqrt{K-1})}+(K-1) \\ &\approx& 2\log{(K+2\sqrt{K})}-\log{(K-2\sqrt{K})}+(K-1) \mbox{ for large K}\\ &=& 2\left(\log{K}+\log{\left(1+\frac{2}{\sqrt{K}}\right)}\right)-\left(\log{K}+\log{\left(1-\frac{2}{\sqrt{K}}\right)}\right) + (K-1) \\ &\approx& \log{K}+\frac{6}{\sqrt{K}}+K-1 \mbox{ for large K} \end{eqnarray}$

where in the last line I used the fact that $\log(1+x)\approx x$ for small $x$. Indeed, we have a function that is going to be dominated, in the limit as $K\rightarrow\infty$, by the linear term. So $F(K)\sim K$ in that limit.

Applying a similar logic to $G(K)$, we do get a slightly more interesting result because you can pull out a factor of $(K-2)\log{\frac{1}{2}}$ from the middle, which actually cancels out the $(K-2)\log{2}$ at the end. With a bit of fiddling around, I think $G(K)\sim 4\sqrt{K}$ for large $K$, just based on the way the terms cancel.

Answer 2

First of all, linear grows faster then logarithmic, so linear+log gives linear.

Second, log of a polynomial or any function that grows like $x^n$ for some fixed $n$ is still log (with a constant), since $\log(x^n) =n \log(x) $.

OK, now we can begin.

For $F(K)$, the first term is the log of a polynomial function of $K$ (it doesn't matter what the degree is), so it is log. The second term is linear times a constant, so it it linear. Their sum is linear+log, which is linear.

For $G(K)$, the first term is, as before, log. The third term is, as before linear. The second term is tricky. The expression inside the log is of the form $\dfrac{K^2+c_1}{2K^2+c_2K+c_3} $ times, when you expand it, $\dfrac{K+c_4\sqrt{K}+c_5}{K+c_6\sqrt{K}+c_7} $ where the $c_i$ are constants. The first term tends to $\frac12$ for large $K$, and the second term tends to $1$ for large $K$, so their product tends to $\frac12$ for large $K$. Therefore the term inside the log tends to $\frac12$, so the log tends to $\log(\frac12)$, which is constant. Therefore, the second term is linear.

Therefore $G(K)$ is linear.

To make these types of problems easier, look up "orders of magnitude" and "big-oh" and "little-oh" operations.