The Gateway to Computer Science Excellence
+1 vote
79 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 by Veteran (58.9k points)
edited by | 79 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)
by (27 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
198,235 comments
104,918 users