search
Log In
1 vote
290 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
in Algorithms 290 views
0
I have a problem with statement $(1)?$
0
the second statement is also false right?
0
yeah answer should be C
0
but any two function we represent as F(n) = Og(n) or G(n) = O(f(n)) right ???
1

no..consider f(n)= n and g(n)= nsinx+1 ..in this case the 2 functions are not comparable.

0
No @magma
0
see 3 scenarios

either f(n) >= g(n) or f(n) < = g(n) or f(n) = g(n)

when f(n) > = g(n) == > g(n) = O(f(n))

when g(n) > = f(n) === >f(n) = O(g(n))

when g(n) = f(n) ==== > then also it's right :3

# confused
0
F(n) = n and G(n) = n^2 , we can say f(n) = O(g(n)) bt cant represent G(n) = o(f(n))
0
when g(n) = f(n) then g(n) = theta(f(n)) and vice versa
0

F(n) = n and G(n) = n^2 , we can say f(n) = O(g(n)) bt cant represent G(n) = o(f(n))

 But in the question they mention "OR"

either of them can be satisfied :3

 

0
Ohk got it

thanks
0
Both are false
0
o sorry wrong example ........ example of somoshree is right

2 Answers

2 votes

The first statement is false. 
Take two functions, $f(n) = 0.5$, $g(n) = sin(n)$.

You cannot compare these two functions using Big-Oh notation.

For more, read here: https://cs.stackexchange.com/questions/1780/are-the-functions-always-asymptotically-comparable

0 votes

Statement 1 is false.

Consider f(n) = 0.5 and g(n) = sin(n)
or, consider f(n) = n and g(n) = 1 when n is even; $n^{2}$ when n is odd.

In both the above cases neither f(n) = Og(n) nor g(n) = Of(n)

 

Statement 2 is false

Consider g(n) = 2n and h(n) = n and f(n) = 10n

 

Other important statements

All the below cases are possible:-

$f(n) = Og(n)$ and $g(n) = Of(n)$ — Case 1

$f(n) = Og(n)$ and $g(n) \neq Of(n)$ — Case 2

$f(n) \neq Og(n)$ and $g(n) \neq Of(n)$ — Case 3

 

Case 1

When f(n) and g(n) are identical both functions can upper bound each other.

 

Case 2

f(n) = n and g(n) = $n^{2}$

 

Case 3

See "Statement 1 is false"

Related questions

1 vote
0 answers
1
306 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 306 views
1 vote
1 answer
2
183 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)))$
asked Nov 1, 2018 in Algorithms Lakshman Patel RJIT 183 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
194 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 194 views
...