0
$\begingroup$

How do you solve something like this?

Find A and B from the following expressions:

  1. Ω(g(n)) + O(g(n)) = A(g(n))
  2. Θ(g(n)) \ Ω(g(n)) = B(g(n))

1 Answers 1

0

Well, I managed to get the answer for both, so for anyone who is having these issues, here are the solutions:

First problem:

Ω(g(n)) = f(n), O(g(n)) = h(n).

From the above we can say: f(n)>=g(n)*k, with n sufficiently large and k a constant (definition of Ω).

If you add a non-negative function to a Ω, it will still remain a Ω.

So now we can write: f(n)+h(n)>=g(n)*k, which yields A=Ω.

Second problem:

Θ(g(n)) = f(n), Ω(g(n)) = h(n). I am making the assumption that all values are greater than 1, given proper constants and a large enough n.

From the above we can say:

g(n)*k1 <= f(n) <= g(n) * k2, (definition of Θ).

h(n)>=g(n) * k, (definition of Ω), and also h(n)/k >= g(n) and multiplying by k2 we get:

h(n) * k2/k >= g(n) * k2

So now we have:

g(n)*k1 <= f(n) <= g(n)*k2 <= h(n) * k2/k which yields

f(n) <= h(n) * k2/k. Now we divide by h(n) and get:

f(n)/h(n) <= k2/k. Now we just multiply by g(n) and get:

f(n)/h(n) <= k2/k * g(n) => B = O.

Hope this will be of some use to someone.