in Algorithms edited by
818 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)$
in Algorithms edited by
818 views

2 Comments

I think both (a) and (c) are false..
1
1
edited by

@Amsar: Yep, a and c are False. But why do you think that b is True? Edit: oOPs. missed the $\log$.

2
2

2 Answers

10 votes
10 votes
Best answer

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

1 comment

@Pragy bhaiya : option $A$ will be true for small -oh$(o)$ right?
0
0
0 votes
0 votes

option B is false 

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

2 Comments

Why do you think A is correct?

Your explanation (?) for option B makes no sense.

For option C, it is not wise to just compare two plots to find the asymptotic complexities. However, you're correct in that $\frac 1 x \neq O \left ( \frac 1{n^2} \right )$

PS: One must learn to be skeptic of proofs by pictures.
0
0

Yes, I missed answering it more precisely, interpreted it as :

+ provided peek at asymptotics using graphs to give counters for statements.

Explanation to option B is bogus.

2
2