search
Log In
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)))$
in Algorithms
edited by
184 views
0
ok c is the answer
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

1 Answer

0 votes
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
2 answers
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
asked Nov 1, 2018 in Algorithms Lakshman Patel RJIT 293 views
1 vote
0 answers
2
308 views
int unknown(int n) { inti, j, k = 0; for (i = n/2; i<= n; i++) for (j = 2; j <= n; j = j * 2) k = k + n/2; return k; } What is the returned value of the above function? (GATE CS 2013) (a) Ѳ(n2) (b) Ѳ(n2 log n) (c) Ѳ(n3) (d) Ѳ(n3 log n)
asked Nov 14, 2017 in Algorithms NIKU 308 views
1 vote
1 answer
3
149 views
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))$
asked Aug 23, 2017 in Algorithms Victor0001 149 views
1 vote
1 answer
4
195 views
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))$
asked Aug 23, 2017 in Algorithms Victor0001 195 views
...