algorytm quicksort

[adacho90]

Niech k >= 2. Podczas sortowania za pomocą Quicksort pewnej tablicy o długości n okazało się, że po każdym wywołaniu funkcji Partition, z parametrem i oraz j określającym odpowiedni fragment tablicy o długości większej niż 2, pozycja p elementu dzielącego spełnia następujący warunek:

p-i <= k lub j-p <= k

Jaki jest rząd złożoności algorytmu?