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