CODEWITHSUNDEEP
complexity-theory
Snyder-66
Snyder-66

Reputation: 19

Asymptotic Notation: Proving Big Omega, O, and Theta

I have a few asymptotic notation problems I do not entirely grasp.

So when proving asymptotic complexity, I understand the operations of finding a constant and the n0 term of which the notation will be true for. So, for example: 

Prove 7n+4 = Ω(n)

In such a case we would pick a constant c, such that it is lower than 7 since this regarding Big Omega. Picking 6 would result in 

7n+4 >= 6n

n+4 >= 0

n = -4

But since n0 cannot be a negative term, we pick a positive integer, so n0 = 1.

But what about a problem like this:

Prove that n^3 − 91n^2 − 7n − 14 = Ω(n^3).

I picked 1/2 as the constant, reaching

1/2n^3 - 91n^2 - 7n -14 >= 0.

But I am unsure how to continue. Also, a problem like this, I think regarding theta:

Let g(n) = 27n^2 + 18n and let f(n) = 0.5n^2 − 100. Find positive constants n0, c1 and c2 such
that c1f(n) ≤ g(n) ≤ c2f(n) for all n ≥ n0.

In such a case am I performing two separate operations here, one big O comparison and one Big Omega comparison, so that there is a theta relationship, or tight bound? If so, how would I go about that?

Upvotes: 1

Views: 1797

Answers (1)

kaya3
kaya3

Reputation: 51053

To show n3 − 91n2 − 7n − 14 is in Ω(n3), we need to exhibit some numbers n0 and c such that, for all n ≥ n0:

n3 − 91n2 − 7n − 14 ≥ cn3

You've chosen c = 0.5, so let's go with that. Rearranging gives:

n3 − 0.5n3 ≥ 91n2 + 7n + 14

Multiplying both sides by 2 and simplifying:

182n2 + 14n + 28 ≤ n3

For all n ≥ 1, we have:

182n2 + 14n + 28 ≤ 182n2 + 14n2 + 28n2 = 224n2

And when n ≥ 224, we have 224n2 ≤ n3. Therefore, the choice of n0 = 224 and c = 0.5 demonstrates that the original function is in Ω(n3).

Upvotes: 2

Related Questions