I want to show that the best-case running time of quicksort at an array with pairwise distinct elements is: $\Omega(n \lg n)$ .
Could I say the following?
At the best case, partition 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)$.
The following $n\times n$ determinant identity is included as eq. 19 on Mathworld's entry for the Chebyshev polynomials of the second kind:
$$U_n(t)=\begin{vmatrix}2 x& 1 & 0 &\cdots &0\\ 1 & 2x &1 &\cdots &0 \\
0 & 1 & 2x &\cdots &0\\0 & 0 & 1 & \ddots & \vdots \\
\vdots & \ddots & \ddots &\...
$\def\b{\begin{bmatrix}}\def\e{\end{bmatrix}}$
Are $\b0&0&a&b\\0&0&c&d\\0&0&0&0\\0&0&0&0\e$ and it's transpose, $a,b,c,d\in \Bbb C$ the only nillpotent degree $2$ 'families' of matrices of size $4\times 4$?
I believe they are, but I wanted to verify.
