edited by
263 views
1 votes
1 votes
If I have f(n)= omega(n) and G(n)= Big O(n) then what would be f(n)*G(n)

also can we compute f(n) / g(n) and f(n)- G(n)
edited by

1 Answer

Best answer
2 votes
2 votes

Part 1 ans:

Let us say here "n" represent some function say h(n) so that we can more intuitively define the function,

Now, if f(n) = Ω(n) means in ours terms we can say f(n) = Ω.h(n) hence similarly g(n) = Ο.h(n) 

Then according to the definition 


f(n) = Ω.h(n) if

f(n) ≥ c.h(n)   and                -----------------(1)


g(n) = O.h(n) if

g(n) ≤ c.h(n)                        -----------------(2)


Now, g(n) ≤ c.h(n) ≤ f(n)

case 1: IF f(n), g(n) and c.h(n) are equal then,

            f(n) * g(n) = [c.h(n)]2

case 2: In all cases f(n) is greater than g(n) according to the definition (1) & (2)

            Notion : f(n) > g(n)

                  or c1.h(n) > c2.h(n) so as due to the const. "c1" f(n) becomes larger than g(n).

Hence in this case: f(n) * g(n) = c1.c2.[h(n)]2.


Part 2 ans: f(n)/g(n) always greater than or equal to 1.


Part 3 ans: f(n)-g(n) is always positive.


selected by

Related questions

0 votes
0 votes
2 answers
1
0 votes
0 votes
2 answers
2
dhruba asked Jun 5, 2023
1,094 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...
0 votes
0 votes
1 answer
3
Chaitanya Kale asked Nov 10, 2022
276 views
Can we write f(2$^{n/a}$) = Θ(2$^{n}$) for any integer a >0?