Proving and Disproving BigO

Question

In proving and disproving Big O questions that explicitly say use the definition to prove and disprove, my question is, is what I am doing correct?

For example you have a question that is g(n) = O(f(n)) ... In order to prove it I was doing the following

g(n) <= C(F(n))
g(n)/F(n) <= C .. then give n=1 and solve for C , which proves it.

The contradiction that I run to when doing this is when i approach a question of disproving this stuff

for example

g(n) =O(F(n)) to disprove it I would do

g(n) >= C(F(n)) and solve for C again . However this leads me to believe that big O can be proved and disproved at once ? which is 100% wrong.

Using real world numbers (Proving)

n^2 + 3 = O(n^2)
(n^2 + 3)/n^2  <= C  assume n = 1 then C >= 3

Disproving

n^2 + 3 = O(n^2)


(n^2 + 3)/n^2  >= C  assume n = 1 then C <= 3

n^2 + 3 = O(n^2)

both of these say that @ n =1 and c = 3 the algorithm is O(n^2) and is NOT O(n^2).

Can anyone help me clarify my confusion and give me a help me learn a good algorithmic way of solving big O questions?

Answer 1

Neither of your techniques work. Let's start with the definition of big-O:

f is O(g) iff there exist C, N such that |f(x)| ≤ C |g(x)| for all x ≥ N

To prove "there exist" type statements, you need to show that, well, the things exist. In the case of big-O proofs, you usually find the things, though proofs of existence don't generally need to be constructive. To build a proof for a "for all" statement, pretend someone just handed you specific values. Be careful you make no implicit assumptions about their properties (you can explicitly state properties, such as N > 0).

In the case of proving big-O, you need to find the C and N. Showing |g(n)| ≤ C|F(n)| for a single n isn't sufficent.

For the example "n²+3 is O(n²)":

 For n ≥ 2, we have: 
    n2 ≥ 4 > 3
      ⇒ n2-1 > 2
      ⇒ 2(n2-1) > (n2-1)+2
      ⇒ 2n2 > (n2-1)+4 = n2+3
 Thus n2+3 is O(n2) for C=2, N=2.

To disprove, you take the negation of the statement: show there is no C or N. In other words, show that for all C and N, there exists an n > N such that |f(n)| > C |g(n)|. In this case, the C and N are qualified "for all", so pretend they've been given to you. Since n is qualified "there exists", you have to find it. This is where you start with the equation you wish to prove and work backwards until you find a suitable n.

Suppose we want to prove that n is not O(ln n). Pretend we're given N and C, and we need to find an n ≥ N such that n > C ln n.

For all whole numbers C, N, let M=1+max(N, C) and n = eM. Note n > N > 0 and M > 0.
Thus n = eM > M2 = M ln eM = M ln n > C ln n. QED.

Proofs of x > 0 ⇒ e^x > x² and "n is not O(ln n)" ⇒ "n is not O(log_b n)" left as exercises.