Proving NOT (n3 \in O(3n^2): We Know What n^3 Is But Not What It May Be - Week 10

In this week’s first lecture we were going over how to prove or disprove that a polynomial is in Big O. While last week the focus was primarily on proving that a polynomial had a growth rate no faster than the polynomial inside the Big O, the start of this week has been focusing on disproving this. Proving something in Big O seems more straight-forward than disproving for these cases. While neither is particularly hard, it feels as if there are more considerations for the negation.  To prove this type of question, you must subtract values that are decreasing the value of the polynomial and multiply terms by n to increase it for comparison. For the polynomial in big O, you can do the same type of modifications to decrease it until the two formulas are easily comparable. Then it is fairly simple to pick B and c.

Disproving it takes a few more steps and I believe a little more thinking. Here is one example of this type of question.

We were asked to disprove n³ e O(3n²):

$c e Â⁺, $B e À, "n e À, n ³ B Þ n³ £ c*3n²

The negation of this is as follows:

"c e Â⁺, "B e À, $n e À, n ³ B Ù n³ > c*3n²

Assume c e Â⁺ and B e À       # generic c, B to introduce "

                Pick n = B + é3cù + 1. Then n e À.

                Then n ³ B        # added some non-negatives to B

                Then n³ = n * n²

                Then n³ > 3cn²     # since n > 3c

                Then n ³ B Ù n³  > 3cn²

Conclude "c e Â⁺, "B e À, $n e À, n ³ B Ù n³ > c*3n²

While this question is a very simple example of the much harder proofs we will be doing, it does show that when choosing n, many things must be considered. The value of n must be greater than or equal to B and the formula itself must take into account the other polynomial and c. Furthermore, as n must be a natural number and c does not have to be, flooring or taking the ceiling is also necessary. In the end, we know that n³ is a polynomial to the third degree, but we don’t know (until we prove it) that n³ is not in the Big O of 3n².