Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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))
share|improve this question

migrated from stackoverflow.com Sep 20 '12 at 11:43

This question came from our site for professional and enthusiast programmers.

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.