Question

Este adevărat că:


$i)\quad \log_{2}n = O(n^2) \\ ii)\quad n = O(\sqrt n)$

?


Furnizați dovezi pentru a vă sprijini răspunsurile.

Answer 1

i.

$log_2 n = O(n^2) \iff \lim\limits_{n\to \infty} \frac{log_2 n}{n^2} \in [0, +\infty).\\\lim\limits_{n\to \infty} \frac{log_2 n}{n^2} = 0 \Rightarrow Adevarat$

ii.

$n = O(\sqrt{n}) \iff \lim\limits_{n\to \infty} \frac{n}{\sqrt{n}} \in [0, +\infty) \\ \lim\limits_{n\to \infty} \frac{n}{\sqrt{n}} = \lim\limits_{n\to \infty} \sqrt{n} = +\infty \Rightarrow Fals$