Qsort

T (n) = T (n - 1) + n - 1

T (n) = (n (n - 1))/2

W (n) ≤ (n (n - 1))/2

n = 0

W (0) = 0≤ (0 (0 - 1))/2

0≤k<n

W (k) ≤ (k (k - 1))/2

T (n) = (n (n - 1))/2

W (n) ≤ W (p - 1) + W (n - p) + n - 1

≤ ((p - 1) (p - 2))/2 + ((n - p) (n - p - 1))/2 + n - 1

≤ (n (n - 1))/2

W (n) = (n (n - 1))/2∈θ (n^2)

Probability : n -some p

A (n) = Underoverscript[∑, p = 1, arg3] 1/n[A (p - 1) + A (n - P)] + n - 1

Underoverscript[∑, p = 1, arg3][A (p - 1) + A (n - P)] = 2Underoverscript[∑, p = 1, arg3] A (p - 1)

A (n) = 2/nUnderoverscript[∑, p = 1, arg3] A (p - 1) + n - 1

n A (n) = 2Underoverscript[∑, p = 1, arg3] A (p - 1) + n (n - 1)

(n - 1) A (n - 1) = 2Underoverscript[∑, p = 1, arg3] A (p - 1) + (n - 1) (n - 2)

n A (n) - (n - 1) A (n - 1) = 2Underoverscript[∑, p = 1, arg3] A (p - 1) + n (n - 1) - 2Underoverscript[∑, p = 1, arg3] A (p - 1) + (n - 1) (n - 2)

n A (n) - (n - 1) A (n - 1) = 2A (n - 1) + 2 (n - 1)

n A (n) = (n + 1) A (n - 1) + 2 (n - 1)

(A (n))/(n + 1) = (A (n - 1))/n + (2 (n - 1))/(n (n + 1))

a_n = (A (n))/(n + 1)

a_n = a_ (n - 1) + (2 (n - 1))/n (n + 1)

a_n ≈ 2 Ln[n]

a_n ≈ 2 Ln[n] = 2 Log[2] Log[n]

(A (n))/(n + 1) ≈ 2 Log[2] Log[n]

A (n) ≈ (n + 1) 2Log[2] Log[n] = 1.38 (n + 1) Log[n] ∈θ (n Log[n])