Search code examples
algorithmanalysis

f(n) = o(g(n)) ve f(n) ≠ Ɵ(g(n))

I'm trying to solve these problems as an example, but I'm stuck. If anyone has an idea, can they help? Show the real relations asymptotically. Show that f (n) and g (n) can be or not.

a. f(n) = o(g(n)) and f(n) ≠ Ɵ(g(n))
b. f(n) = Ɵ(g(n)) and f(n)=o((n))
c. f(n) = Ɵ(g(n)) and f(n) ≠O(g(n))
d. f(n)= Ω (g(n)) and g(n)= Ω (h(n)) and h(n)= Ω (f(n)) if f(n)= Ɵ(h(n)) Here f, g and h are asymptotic positive functions.
Solution

  • you can take these functions:

    a:

    f(n) = x
g(n) = x^2

    b isn't possible since the definition of f(n)=o(g(n)) is f(n)=O(g(n)) and f(n) ≠ Ɵ(g(n))

    c isn't possible since the definition of f(n)=Ɵ(g(n)) is f(n)=O(g(n)) and f(n)=Ω(g(n))