0

Hi I am studying Asymptotic analysis but generally find difficulty in identifying the greater of two functions ? Like ex.

$$f(n) = ((n^2)(\log_2(n))\\ g(n) = n((\log_2(n))^{10})$$

(here log are to base 2).

So, I know log to base 2 means $\log n\over \log 2$. Can anyone guide me how to find larger of two functions ?

abiessu
  • 8,115
Kunal
  • 1

1 Answers1

2

Hint:

How do $h(n)=n$ and $k(n)=(\log_2(n))^9$ compare? How do these functions compare to $f$ and $g$ as given?

Further hint: with the functions given, it is common to use induction to prove which is larger beyond a certain bound.

If we start with $n=2^{100}$, we get $h(n)=2^{100}$ and $k(n)=100^9$. Since $2^{10}\gt 1000$ we have $h(2^{100})=\left(2^{10}\right)^{10}\gt 1000^{10}\gt 100^9,$ which means we know at least one point where $h(n)\gt k(n).$

Another direction is that we could compare slopes of the two functions. If we take the derivative of each of $h(n), k(n)$ we get $h'(n)=1, k'(n)={9\log_2^8(n)\over n\log 2},$ so now we can compare $h_1(n)=n$ with $k_1(n)={9\log_2^8(n)\over\log 2}.$ Repeating this process, it is easy to see that the last comparison will be $h_9(n)=n$ with $k_9(n)={9!\over \log^9 2}.$ It is clear that $n$ is greater than a constant function for all large $n,$ so now we work backwards and see that in each case there is a "large enough" value such that $h_i(n)\gt k_i(n)$, and thus, since the slope of $h(n)$ is greater than that of $k(n)$ for all $n$ large enough and since there is a value where $h(n)\gt k(n)$, then for all large enough $n, h(n)\gt k(n).$

Note that this derivative direction has steps which are glossed over and also that there is probably an easier way, but this mechanism at least demonstrates the required inequality.

abiessu
  • 8,115