Question

Are the following TRUE or FALSE. explain
n2 = O(n2)
n3 = O(n2)
n log n = O(n2)
n2 = O(n log2 n)

Answer 1

Answer on Question #63787 – Math – Algorithms | Quantitative Methods

Question

Are the following TRUE or FALSE. Explain

$$n2 = O(n2)$$ $$n3 = O(n2)$$ $$n \log n = O(n2)$$ $$n2 = O(n \log 2 n)$$

Solution

a) $n^2 = O(n^2)$

**TRUE.** We can see this if we set $c = 1$, then $n^2 \leq c n^2 = n^2$ for all $n \geq 1$.

Thus, the definition of big-0 holds for $c = 1$ and $n_0 = 1$.

b) $n^3 = O(n^2)$

**FALSE.** For it to be true, we would need that there exist positive constants $c$ and $n_0$ such that $n^3 \leq c n^2$ for all $n \geq n_0$. By dividing both sides by $n^2$, we see that "$n^3 \leq c n^2$ for all $n \geq n_0$" is true if and only if "$n \leq c$ for all $n \geq n_0$" is true, but clearly there are no constants $c$ and $n_0$ for which the last statement is true.

c) $n \log n = O(n^2)$

**TRUE.** Because $\ln(1 + x) \leq x$ for all $x > -1$, hence $\ln(1 + x) \leq (x + 1) - 1 < 2(x + 1)$.

Therefore, $\log n = O(n)$. There exist positive constants $c$ and $n_0$ such that $\log n \leq c n$ for all

$n \geq n_0$. Multiplying both sides by $n$ gives $n \log n \leq c n^2$ for all $n \geq n_0$ for the same positive constants $c$ and $n_0$, so $n \log n = O(n^2)$.

d) $n^2 = O(n \log^2 n)$

**FALSE.** First, note that $n^2 = O(n \log^2 n)$ if and only if there exist positive constants $c$ and $n_0$ such that $n^2 \leq c n \log^2 n$ for all $n \geq n_0$, which holds if and only if

$$\frac{n^2}{n \log^2 n} \text{ for all } n \geq n_0$$

By cancelling out the $n$ from the numerator and the denominator, we can rewrite expression in (1) as

$$\frac {n}{\log^ {2} n} \leq c \text{ for all } n \geq n _ {0}.$$

Writing $n = n^{\frac{1}{2}}n^{\frac{1}{2}}$, we see that the last statement is true if and only if

$$\left[ \frac {n ^ {\frac {1}{2}}}{\log n} \right] ^ {2} \leq c \text{ for all } n \geq n _ {0}.$$

Because we know that $\log n = o\left(n^{\frac{1}{2}}\right)$ (in other words, $\lim_{n\to \infty}\frac{\log n}{\sqrt{n}} = 0$), we have that

$$\frac {n ^ {\frac {1}{2}}}{\log n} \rightarrow \infty \text{ as } n \rightarrow \infty.$$

So $\left[\frac{n^{\frac{1}{2}}}{\log n}\right]^2 \leq c$ cannot be true for all $n \geq n_0$ and for a constant $c$.

Answer: TRUE, FALSE, TRUE, FALSE.

www.AssignmentExpert.com