1
$\begingroup$

I want to demonstrate this relation. I know that $f(n)=\Theta(g(n))$ when $\exists c_1>0, c_2>0, n_o\in \mathbb{N} \mid \forall n \geq n_0$ for which: $$c_1g(n) \leq f(n) \leq c_2g(n)$$ For the first part of the relation, I have $c_1n^2 \leq nlog_{10}(n)$. How can I now demostrate that these $c_1$ and $n$ exist (or better, don't exist, since I know that the initial equation is wrong)?

EDIT: Sorry, I forgot to say. I can't use logarithms, only the definition of $\Theta$

$\endgroup$
3
$\begingroup$

If you can use calculus, it is fairly simple. Suppose that there exist $c_1>0$ such that $c_1\le \frac{n\log_{10}(n)}{n^2}$ for all $n$ large enough. Take the limit: $$c_1\le \lim_{n\rightarrow \infty}\frac{n\log_{10}(n)}{n^2}=\lim_{n\rightarrow \infty}\frac{\log_{10}(n)}{n}=0$$ contradiction.

In other words you have proved that $n\log_{10}(n)=o(n^2)$, so $n\log_{10}(n)\ne\Theta(n^2)$

$\endgroup$
0
$\begingroup$

Well take $c_1\geq10^{-t}$ for some $t$ then you have that for $n=10^{2t}$ for example that $$c_110^{4t}\leq 10^{2t}2t\\2t\geq c_110^{2t}\geq10^t$$ But $2t< 10^t$ for any $t\geq1$ contradiction; hence there doesn't exist such $c_1$ since by assumption $t$ is arbitrary

$\endgroup$
0
$\begingroup$

$$\lim_{n\to\infty}\frac{n\log_{10}n}{n^2}=\lim_{n\to\infty}\frac{\log_{10} n}n=0$$

Then there exists some $N\in\Bbb N$ such that $n\log_{10} n<c_1n^2$ whenever $n\ge N$.

$\endgroup$
-1
$\begingroup$

A little example ,make a sense . $$n=100 \to nlogn=200 ,n^2=10^4\\n=10^5 \to nlogn=5\times 10^5 ,n^2=10^{10}$$ does it make a sense ?

$\endgroup$

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.