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

You seem to be making the mistake in assuming that if g = O(f) then you cannot have f = O(g) or that f >= C * g it would mean f is not O(g).

Showing that g = O(f) involves finding a C such that g <= C*f. Showing that f = O(g) involves finding a D (need not be same as C) such that f <= D*g. Note, the C and D could be different. It could very well happen that, for instance 10*g <= f <= 100*g.

For instance consider f(n) = n and f(n)= 2n.

now n <= 1* 2n so f(n) = O(g(n)). Here C = 1.

Also, 2n <= 10*n, so g(n) = O(f(n)). Here C = 10.

Like Big-O, there are others, like Omega and Theta. I suggest you read about Theta.