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.

CodePudding user response：

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).