Best-Case Running Time of QuickSort: $\Omega(n \lg n)$

[evinda]

Hello! (Wave)

The following pseudocodes are given:

 quicksort(A,p,r)
     if p<r then
        q<-partition(A,p,r)
        quicksort(A,p,q-1)
        quicksort(A,q+1,r)

   partition(A,p,r){
      x<-A[r]
      i<-p-1
      for j<-p to r-1
           if A[j]<=x then
              i<-i+1
              swap(A[i],A[j])
      swap(A[i+1],A[r])
      return i+1

I want to show that the best-case running time of [m] quicksort [/m] at an array with pairwise distinct elements is:
$\Omega(n \lg n)$ .Could I say the following?At the best case, [m] partition [/m] produces two subproblems of size at most $\frac{n}{2}$ each of them, given that the one has size $ \lfloor \frac{n}{2} \rfloor $ and the other $ \lceil \frac{n}{2} \rceil-1$.
The recurrence relation for the execution time is:

$$T(n) \leq 2T\left( \frac{n}{2} \right) + \Theta(n)$$

and from Master Theorem we deduce that $T(n)=O(n \log n)$.Or do we have to solve the recurrence relation $T(n)=\min_{1 \leq q \leq n-1} (T(q)+T(n-q-1)+\Theta(n))$? (Thinking)

 

[Future Bruno]

Yes, you may use the Master Theorem to show that the best-case running time of quicksort with pairwise distinct elements is $\Omega(n \log n)$. You can also solve the recurrence relation $T(n)=\min_{1 \leq q \leq n-1} (T(q)+T(n-q-1)+\Theta(n))$ to show the same result.