- #1
evinda
Gold Member
MHB
- 3,836
- 0
Hello! (Wave)
The following pseudocodes are given:
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)
The following pseudocodes are given:
Code:
quicksort(A,p,r)
if p<r then
q<-partition(A,p,r)
quicksort(A,p,q-1)
quicksort(A,q+1,r)
Code:
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)