title: Big theta notation of insertion sort algorithm
body: <p>I'm studying asymptotic notations from the book and I can't understand what the author means. I know that <code>if f(n) = Θ(n^2) then f(n) = O(n^2)</code>. However, I understand from the author's words that for insertion sort function algorithm <code>f(n) = Θ(n)</code> and <code>f(n)=O(n^2)</code>.</p>
  
  <p>Why? Does the big omega or big theta change with different inputs?</p>
  
  <p>He says that:</p>
  
  <blockquote>
    <p>"The Θ(n^2) bound on the worst-case running time of insertion sort, however, does not imply a Θ(n^2) bound on the running time of insertion sort on every input. "</p>
  </blockquote>
  
  <p>However it is different for big-oh notation. What does he mean? What is the difference between them?</p>
  
  <p>I'm so confused. I'm copy pasting it below:</p>
  
  <blockquote>
    <p>Since O-notation describes an upper bound, when we use it to bound the worst-case running
    time of an algorithm, we have a bound on the running time of the algorithm on every input.
    Thus, the O(n^2) bound on worst-case running time of insertion sort also applies to its running
    time on every input. The Θ(n^2) bound on the worst-case running time of insertion sort,
    however, does not imply a Θ(n^2) bound on the running time of insertion sort on every input.
    For example, when the input is already sorted, insertion sort runs in
    Θ(n) time.</p>
  </blockquote>