title: What is the difference between O, Ω, and Θ?
body: <p>I am learning algorithm analysis. I am having trouble understanding the difference between O, Ω, and Θ.</p>
  
  <p>The way they're defined is as follows:</p>
  
  <blockquote>
    <ul>
    <li><code>f(n) = O(g(n))</code> means <code>c · g(n)</code> is an
    upper bound on <code>f(n)</code>. Thus there exists
    some constant <code>c</code> such that <code>f(n)</code> is
    always ≤ <code>c · g(n)</code>, for large enough <code>n</code>
    (i.e., <code>n ≥ n0</code> for some constant <code>n0</code>).</li>
    <li><code>f(n) = Ω(g(n))</code> means <code>c · g(n)</code> is a
    lower bound on <code>f(n)</code>. Thus there exists
    some constant <code>c</code> such that <code>f(n)</code> is
    always ≥ <code>c · g(n)</code>, for all <code>n ≥ n0</code>.</li>
    <li><code>f(n) = Θ(g(n))</code> means <code>c1 · g(n)</code> is an upper bound on <code>f(n)</code> and <code>c2 · g(n)</code> is a
    lower bound on <code>f(n)</code>, for all <code>n ≥ n0</code>.
    Thus there exist constants <code>c1</code> and <code>c2</code>
    such that <code>f(n) ≤ c1 ·g(n)</code> and <code>f(n) ≥
    c2 ·g(n)</code>. This means that <code>g(n)</code>
    provides a nice, tight bound on <code>f(n)</code>.</li>
    </ul>
  </blockquote>
  
  <p>The way I have understood this is:</p>
  
  <ul>
  <li><code>O(f(n))</code> gives worst case complexity of given function/algorithm. </li>
  <li><code>Ω(f(n))</code> gives best case complexity of given function/algorithm. </li>
  <li><code>Θ(f(n))</code> gives average case complexity of given function/algorithm. </li>
  </ul>
  
  <p>Please correct me if I am wrong. If it is the case, time complexity of each algorithm must  be expressed in all three notations. But I observed that it's expressed as either O, Ω, or Θ; why not all three?</p>