The Gateway to Computer Science Excellence

+1 vote

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

$(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

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

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))

But in the question they mention "OR"

either of them can be satisfied :3

0

Option (C) is the correct

See here

https://cs.stackexchange.com/questions/1780/are-the-functions-always-asymptotically-comparable

+2 votes

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

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)

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

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

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

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

See "Statement 1 is false"

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,314 answers

198,358 comments

105,083 users