edited by
803 views
6 votes
6 votes

Find the False statement.

  1. $O(2^n) = O(3^n)$
     
  2. $O(\log n^2) = O(\log n)$
     
  3. $f(n) = O \left ( (f(n))^2 \right )$
     
  4. $2^{2 \log n} (\log n) = O(n^2 \log n)$
edited by

2 Answers

Best answer
10 votes
10 votes

A, C are False. B, D are True.


What is $O(g(n))$?

It is the set of all functions that grow no faster than $g(n)$.
$$O(g(n)) = \left \{ f(n) : \substack{\text{there exist positive constants $c$ and $n_0$ such that}\\[0.5em] 0 \leq f(n) \leq c \cdot g(n)\; \text{ for all } n \geq n_0} \right \}$$

What does it mean to say $f(n) = O(g(n))$?

This is an abuse of notation (but not a misuse!)

When we say $f(n) \color{red}{=} O(g(n))$, we actually mean $f(n) \;\color{red}{\in}\; O(g(n))$, that is, the function $f(n)$ is an element of the set of all functions that grow no faster than $g(n)$. In other words, $f(n)$ doesn't grow faster than $g(n)$

Note: We are allowed to abuse the notation because it makes life easier. However, we must take care not to misuse the notation!

We should make sure, however, to understand the precise meaning of the notation so that when we abuse, we do not misuse it. - CLRS (3rd edition, Page 44)

If $A$ and $B$ are two sets, what does it mean to say $A = B$?

It means that every element in $A$ also exists in $B$, and every element in $B$ also exists in $A$.


Coming back to the question,

Option A: False

$O(2^n)$ is a set of all functions that grow at most as fast as $2^n$.
$O(3^n)$ is a set of all functions that grow at most as fast as $3^n$.

Consider the function $2.5^n$. It belongs in $O(3^n)$, but not in $O(2^n)$. Hence, the two sets can't possibly be equal.

Option B: True

$\log \left ( n^2 \right ) = 2 \log n$.

Since constant multiplicative factors do not matter in asymptotic complexity, $O(\log(n^2)) = O(\log n)$

Option C: False.

As mentioned by amarVashishth, $\dfrac 1 x$ grows faster than $\dfrac 1 {x^2}$. Hence, $f(x) \notin O(f^2(x))$

Options D: True.

Let the base of the $\log$ be $2$ (anything will work).

$2^{2 \log n} \cdot \log n = \left ( 2^{\log n} \right )^2 \cdot \log n = (n)^2 \cdot \log n$.

selected by
0 votes
0 votes

option B is false 

option C is false : taking $f(x) = \frac{1}{x}$

Answer:

Related questions

0 votes
0 votes
1 answer
1
gshivam63 asked May 31, 2016
462 views
It is true or false..(log n)! and (log log n)! are polynomially bounded?What does polynomially bounded means?
1 votes
1 votes
1 answer
2
UK asked Dec 29, 2015
408 views
Ans given is D. Is it because, in analyzing this we would ignore the constants involved in the equation?
0 votes
0 votes
2 answers
3