0
$\begingroup$

I am having trouble knowing how to find out whether a given logarithmic function, |f(x)|, is an element of the set of all functions less than or equal to C * |g(x)| where g(x) is a non-logarithmic function for some C and k such that x > k.

For example:

Say I am trying to prove that:

|N log N| <= C * |N^3| for some C and k where x > k

A way to establish whether this statement is true would be to solve for C. If C is not a function of N, then the statement holds true. To better be able to divide f(x) by g(x) to get a useful value would be to increase f(x). If f'(x) is still less than C * g(x) then we can still divide it by g(x) to get a useful value for C that can help prove whether the initial statement is true.

My struggle is what do I do if I am comparing a logarithmic function to a non-logarithmic function? It seems like it would be extremely difficult to increase N log N in to something that can be divided by N^3. Is there a way to do this? I have been doing research on logarithms and have not, so far, been able to find a way to do this.

$\endgroup$
0
$\begingroup$

You could use limits to prove this, or you could prove it algebraically as follows:

For all $n \ge 1$, $$n \le e^n$$ $$ \log n \le \log e^n$$ $$ \log n \le n$$ $$ n \cdot \log n \le n \cdot n^2$$ $$ n \log n \le n^3$$ Hence, $$n \log n = O(n^3)$$

$\endgroup$
  • $\begingroup$ I understand everything except the second to last step where you multiply log n by n and n by n^2. Why are you able to do that? $\endgroup$ – Darien Springer Oct 17 '19 at 21:40
  • $\begingroup$ is it because it is not an equality statement but an inequality statement? $\endgroup$ – Darien Springer Oct 17 '19 at 21:54
  • $\begingroup$ Exactly. The statement is an inequality, so there is no requirement to multiply both sides by the same quantity - as long as the inequality still holds. In this case $n \le n^2$ for $n \ge 1$, so if $a \le b$, then $an \le bn^2$. This sort of technique is used all the time with inequalities. $\endgroup$ – RyRy the Fly Guy Oct 17 '19 at 22:25
  • $\begingroup$ If you are satisfied with your answer, then please click the green check to close the post. Thanks! $\endgroup$ – RyRy the Fly Guy Oct 17 '19 at 22:28
  • $\begingroup$ Also how does log e^n = n? Wouldn't it equal whatever exponent value would make e = n? $\endgroup$ – Darien Springer Oct 17 '19 at 22:50
0
$\begingroup$

$$\lim_{n\to\infty}\frac{n\log{(n)}}{n^3}=0\implies n\log{n}=o(n^3)$$ i.e. the statement is true $\forall \,C\gt0$ as long as $k$ is suitably chosen.

$\endgroup$
  • $\begingroup$ Yes but can I prove this more algebraically? In this case I have to just assume that as n approaches infinity that n^3, for some value of C and k when x > k, will grow faster than n log n forever after that point. Because if I just prove that one function will reach a point where it grows faster than the other using the assumption that one grows faster than the other, then haven't I used circular reasoning? Or am I misunderstanding your reasoning here? $\endgroup$ – Darien Springer Oct 17 '19 at 20:44
  • $\begingroup$ Maybe you could use this question? $\endgroup$ – Peter Foreman Oct 17 '19 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.