# Asymptotic Notations

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
0
I have a problem with statement $(1)?$
0
the second statement is also false right?
0
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

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.

## 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
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)
1 vote
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)))$
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))$