1,077 views
1 votes
1 votes
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

2 Answers

0 votes
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 votes
1 votes
0 answers
1
NIKU asked Nov 14, 2017
687 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...
1 votes
1 votes
1 answer
3
2 votes
2 votes
3 answers
4
shubhojit1412 asked May 25, 2019
2,206 views
If $T1(n) = \Theta(f(n))$&$T2(n) = \Theta(f(n))$Then, Is $T1(n) + T2(n) = O(f(n))$If yes, then how?