title: Why is this the cost?
body: <p>The algorithm of the Quicksort is:</p>
  
  <pre><code>Quicksort(A,p,r)
        if p&lt;r then
           q&lt;- partition(A,p,r)
           Quicksort(A,p,q-1)
           Quicksort(A,q+1,r)
  </code></pre>
  
  <p>According to my notes,the cost of Quicksort(A,1,n) is T(n)=T(q)+T(n-q)+ cost of partition.</p>
  
  <p>Why is the cost like that and not : T(n)=T(q-1)+T(n-q)+cost of partition?</p>
  
  <p>And also why is the cost of the worst case T(n)=T(n-1)+Θ(n) ?</p>