LOWER BOUND

(a) Local exchange only

each accomplishes in undoing one environment
5 1 4 7 2 has inversions (5,1),(5,4),(5,2),(4,2),(7,2)
(n n-1 ...2 1) has $n(n-1)/2$ inversions
$\Rightarrow O(n^{2}/2)$ lower bound

(b) lower bound on comparison based sorting
example: a b c - there are 3! outputs.
(for n numbers there are n! outputs)
Every decision tree to sort n numbers must have atleast n! leaf nodes
Every decision tree to sort n numbers must have atleast 2n! - 1 nodes
Every decision tree to sort n numbers must have depth atleast $\log_{2} n!$ leaf nodes
Depth is the lower bound worst case time complexity for this class of algorithms
$\log_{2} n!=log_{2} (n * (n-1) * (n-2) * (n-3) ...... 1)$
$\log_{2} n!=log_{2} (n) + log_{2} (n-1) + log_{2} (n-2) + log_{2} (n-3) ...... + log_{2} (1)$
$\log_{2} n!=\sum_{j=1}^{n} \log_{2} j$
$\leq \int_{1}^{n} \log_{2} xdx$
$=(x\log x -x)\vert _{1}^{n}$
$=n\log n -n$

Lower Bound on Comparison-Based Sorting Algorithm
Decision Tree for 3 numbers

Depth of binary tree with $n!$ leaves
$\geq \log_{2} n!$
$\geq \int \log x dx$
$\geq n\log n-1.5n$