title: Proving and Disproving BigO
body: <p>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?</p>
  
  <p>For example you have a question that is g(n) = O(f(n)) ... In order to prove it I was doing the following</p>
  
  <pre><code>g(n) &lt;= C(F(n))
  g(n)/F(n) &lt;= C .. then give n=1 and solve for C , which proves it.
  </code></pre>
  
  <p>The contradiction that I run to when doing this is when i approach a question of disproving this stuff</p>
  
  <p>for example </p>
  
  <p>g(n) =O(F(n)) to disprove it I would do </p>
  
  <p>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.</p>
  
  <p>Using real world numbers
  (Proving)</p>
  
  <pre><code>n^2 + 3 = O(n^2)
  (n^2 + 3)/n^2  &lt;= C  assume n = 1 then C &gt;= 3
  
  Disproving
  
  n^2 + 3 = O(n^2)
  
  
  (n^2 + 3)/n^2  &gt;= C  assume n = 1 then C &lt;= 3
  
  n^2 + 3 = O(n^2)
  </code></pre>
  
  <p>both of these say that @ n =1 and c = 3 the algorithm is O(n^2) and is NOT O(n^2).</p>
  
  <p>Can anyone help me clarify my confusion and give me a help me learn a good algorithmic way of solving big O questions?</p>