Consider the following python implementation of the Heap Sort algorithm:

def heapsort(lst):
    length = len(lst) - 1
    leastParent = length // 2
    for i in range (leastParent, -1, -1):
        moveDown(lst, i, length)

    for i in range(length, 0, -1):
        if lst[0] > lst[i]:
            swap(lst, 0, i)
            moveDown(lst, 0, i - 1)

def moveDown(lst, first, last):
    largest = 2 * first + 1
    while largest <= last:
        # right child is larger than left
        if (largest < last) and (lst[largest] < lst[largest + 1]):
            largest += 1

        # right child is larger than parent
        if lst[largest] > lst[first]:
            swap(lst, largest, first)
            # move down to largest child
            first = largest;
            largest = 2 * first + 1
            return # exit

def swap(lst, i, j):
    tmp = lst[i]
    lst[i] = lst[j]
    lst[j] = tmp

I have been able to formally prove that worst-case is in $\Theta(n \log(n))$ and that the best-case is in $\Theta(n)$ (some might argue the best-case is in $\Theta(n \log(n))$ as well since that's what most searches on the internet will return but just think of what happens when an input list where all of the elements are the same number).

I have showed both upper and lower bounds of the worst and best-case by realizing that the route taken by moveDown function is dependent on the height of the heap/tree and whether the elements in the list are distinct or the same number across the whole list.

I have not been able to prove the average case of this algorithm which I know is also in $\Theta(n \log(n))$. I do know, however, that I am supposed to consider an input set or family of lists of all length $n$ and I am allowed to make an assumption such as that all of the elements in the list are distinct. I confess that I am not good at average-case analysis and would really appreciate it if someone could give a complete and thorough proof(including the exact expressions especially of the number of inputs) as it would help me understand the concept a great deal.

  • 3
    $\begingroup$ If best and worst cases are $\Theta(n \log n)$, all cases fall in between and their average does too. $\endgroup$ – vonbrand Aug 12 '19 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.