1

6n^4 −3n^2 +3 is Ω(n4)

Hello, I need to determine whether this statement is true or false.

Any help is appreciated.

Thank you

I am leaning towards true due to the n^4, however the omega complexity is making me doubt this.

I believe if it was big O it would be a true statement.

Ella
  • 23
  • 3
  • Does this answer your question? [What exactly does big Ө notation represent?](https://stackoverflow.com/questions/10376740/what-exactly-does-big-%d3%a8-notation-represent) – Nelfeal Nov 20 '22 at 13:01
  • You need to find out what the definition of big omega is, and then see if you can prove whether the statement is true or false. If you find yourself "leaning true" or doubting, you're not approaching the problem in the right way -- you can't feel or intuit the answer, you have to prove it. – Paul Hankin Nov 20 '22 at 14:20

1 Answers1

0

f is Omega(g) if there exist constants c and n0 such that for all n > n0, f(n) >= c * g(n). For us, we need to evaluate whether there are constants n0 and c such that 6n^4 - 3n^2 + 3 > cn^4 for all n > n0. If we choose n = 5 we get...

6n^4 - 3n^2 + 3 > 5n^4
n^4 - 3n^2 + 3 > 0

Using the quadratic formula we can find values for n^2 where the LHS equals zero:

n^2 = [-b +- sqrt(b^2 - 4ac)] / 2a
    = [3 +- sqrt(9 - 12] / 2

But the discriminant is negative, which means there are no real values of n^2 where the LHS equals 0. This means that the LHS has no roots and never crosses the X-axis; it is either always positive or always negative. We can see which is the case easily by plugging in 0:

0^4 - 30^2 + 3 = 3 > 0

So, with the choice of c=5, our inequality is true for all n; we are free to choose any n0, e.g., n0 = 1 works.

Because there exists a pair c=5 and n0=1 which gives us f(n) = 6n^4 - 3n^2 + 3 > 5n^4 = cg(n) for all n > n0, we can say that f is Omega(g).

Patrick87
  • 27,682
  • 3
  • 38
  • 73