# Asymptotic Notations with condition

1 vote
184 views
Identify the FALSE statement:
$A)$ $f(n)=\theta(f(\frac{n}{2})$  $implies$  $f(n^{2})=\theta(f(\frac{n^{2}}{2}))$

$B)$ $f(n)=O(g(n))$  $implies$  $log(f(n))=O(log(g(n)))$ where $n\geq2$

$C)$ $f(n)=O(g(n))$  $implies$  $2^{f(n)}=O(2^{g(n)})$

$D)$ $f(n)+g(n)=\theta(Max(f(n),g(n)))$

edited
0
0
$C$ is the answer.
0

suppose F(n)=2logn and G(n)=logn​​​​​​  here f(n)=O(g(n))

but

2f(n)=22logn

2g(n)=2logn

now assume 2logn=x

then 2f(n)= x2

and
2g(n)=x

so 2f(n)=O(2g(n)) is not hold

this was expalnation ??

0
f(n)=2logn and g(n)=logn​​​​​​  here f(n)=O(g(n))??

i think f(n)=logn and g(n)=2logn​​​​​​  here f(n)=O(g(n))
how you write this?
0
take f(n)=2n, g(n)=n  then, f(n)<=c.g(n) for c>=2; i.e., f(n)=O(g(n))

but,here 2^f(n) != O( 2^g(n) )
0
I think

take f(n)=2n, g(n)=n  then, f(n)<=c.g(n) for c>=2; i.e., f(n)=O(g(n))
0
yes..corrected
0
yes
0

option c is wrong.

suppose F(n)=logn and G(n)=2logn​​​​​​ then

2^logn=2^2logn​​​​​​ now assume 2^logn=x

then it becomes x=x^2(which are not equal)

## Related questions

1 vote
1
293 views
Consider the following statements: $(1)$ Any two functions $f,g$ are always comparable under big Oh,that is $f=O(g)$ or $g=O(f)$ $(2)$ If $f=O(g)$ and $f=O(h)$ then $g(n)=\theta(h)$ $A)$ $(1)$ is true $(2)$ is false $B)$ $(1)$ is false $(2)$ is true $C)$ Both are false $D)$ Both are true
1 vote
Let f(n), g(n) &amp; h(n) be 3 non-negative functions defined as follows: $f(n) = O(g(n))\; \; \; g(n) \neq O(f(n))$ $g(n) = O(h(n))\; \; \; h(n) = O(g(n))$ Which of the following is false? (A). f(n) + g(n) = O(h(n)) (B). f(n) = O(h(n)) (C). $h(n) \neq O(f(n))$ (D). $f(n).h(n) \neq O(g(n).h(n))$
Let f(n), g(n) &amp; h(n) be 3 non-negative functions defined as follows: $f(n) = O(g(n))\; \; \; g(n) \neq O(f(n))$ $g(n) = O(h(n))\; \; \; h(n) = O(g(n))$ Which of the following is false? (A). f(n) + g(n) = O(h(n)) (B). f(n) = O(h(n)) (C). $h(n) \neq O(f(n))$ (D). $f(n).h(n) \neq O(g(n).h(n))$