To prove or disprove that $f(n) \in o(g(n))$ for the given functions:

• $f(n) = n^{1.5} + \log_2 n$
• $g(n) = n^2$

we need to determine whether $f(n)$ is asymptotically smaller than $g(n)$, which means that:

$\lim_{{n \to \infty}} \frac{f(n)}{g(n)} = 0$

Step-by-Step Analysis

1. Define the ratio $\frac{f(n)}{g(n)}$:

$\frac{f(n)}{g(n)} = \frac{n^{1.5} + \log_2 n}{n^2}$

2. Simplify the expression:

$\frac{f(n)}{g(n)} = \frac{n^{1.5}}{n^2} + \frac{\log_2 n}{n^2}$

$= \frac{1}{n^{0.5}} + \frac{\log_2 n}{n^2}$

3. Analyze the limit as $n \to \infty$:

We need to evaluate:

$\lim_{{n \to \infty}} \left( \frac{1}{n^{0.5}} + \frac{\log_2 n}{n^2} \right)$

• Consider the first term:

$\lim_{{n \to \infty}} \frac{1}{n^{0.5}} = 0$

• Consider the second term:

$\lim_{{n \to \infty}} \frac{\log_2 n}{n^2}$

To compute this, notice that $\log_2 n$ grows much more slowly than $n^2$. Thus, we apply L'Hopital's Rule:

$\lim_{{n \to \infty}} \frac{\log_2 n}{n^2} = \lim_{{n \to \infty}} \frac{\frac{d}{dn} (\log_2 n)}{\frac{d}{dn} (n^2)} = \lim_{{n \to \infty}} \frac{\frac{1}{n \ln 2}}{2n} = \lim_{{n \to \infty}} \frac{1}{2n^2 \ln 2} = 0$

4. Combine the limits:

$\lim_{{n \to \infty}} \left( \frac{1}{n^{0.5}} + \frac{\log_2 n}{n^2} \right) = 0 + 0 = 0$

Conclusion

Since the limit is 0, we have:

$f(n) \in o(g(n))$

Therefore, the statement is true: $f(n) = n^{1.5} + \log_2 n \in o(n^2)$.

Would you like more details or have any questions?

Here are 5 related questions to consider:

1. What is the definition of Big-O notation and how does it differ from Little-o?
2. How can L'Hopital's Rule be applied in other asymptotic analyses?
3. What are examples of other functions $f(n)$ and $g(n)$ where $f(n) \in o(g(n))$?
4. How does the logarithmic function compare to polynomial functions in terms of growth rate?
5. What are some applications of asymptotic analysis in computer science?

Tip: Remember, $f(n) \in o(g(n))$ implies that $f(n)$ grows strictly slower than $g(n)$ as $n \to \infty$.