Enroll today in this bundle of courses to gain experience in the logistics of pen testing, Linux fundamentals, vulnerability assessments, detecting live systems, and more! This series, valued at $3,000, is free for Premium members, Team Accounts, and Qualified Experts.

For quicksort: The key is the recursion. Assuming a perfect pivot (and a power of 2 size of the array), the amount of time it takes to sort a given size array, T(n), is:

T(n) = T(n/2) + T(n/2) + n

It took n operations to partition the array and it will take however long it takes to sort half of the array TWICE (each half) to finish the sort.

We also know that an array of size 1 is already sorted. This gives you a non-homogeneous recurrance equation. You solve the equation (by converting to a homogeneous equation) and you find that this "perfect pivot" sort has a closed form that is O(n lg n).

Alternatively, think about how many recursive calls will be needed for sorting a size N array. Assuming perfect partition, we need a depth of lg n recursive calls (n, n/2, n/4, n/8, n/16, ..., 2, 1; there are lg n numbers in this sequence and the sequence represents the size of the section of the array being sorted at each recursive call). If you think about ALL of the recursive calls, the calling diagram is a full binary tree (rooted at the call with size n which has two children, the call to sort the left half of the array (size n/2) and the call to sort the right half of the array (size n/2) and so on.

Does that function call diagram make sense? Total complexity is the total of work done in every node. Since the work is proportional to the size of the section of the array being sorted, each level in the full binary tree contributes O(n) work (each level processes the whole array, one piece per node). Thus the total work is proportional to the height of the full binary tree times n. But there are lg n levels in this binary tree so the total complexity of the sort is O(n lg n).

Hope this helps. Getting a feel for complexity is a challenge (learning how to find and solve recurrance equations can be very helpful if you plan on doing a lot of this).

-bcl