As a toy example, we showcase this method on the comparison-based sorting problem:
Given an unsorted array of \(n\) objects, sort them according to the total order \(\leq\).
It is well-known, that this problem cannot be solved with \(o(n \log(n))\) comparisons and thus needs at least \(\Omega(n \log(n))\) total time. As the runtime of MergeSort matches this lower bound, the problem is in \(\Theta(n \log(n))\). But can this runtime be homogeneously distributed over partial solutions? In order to answer this question, we first must define what the algorithm should produce as partial solutions.
Given an unsorted array of \(n\) objects, enumerate them from smallest to largest according to the total order \(\leq\).
As it takes \(\Omega(n)\) time to find the smallest object, every algorithm needs at least linear preprocessing time or linear delay to solve this enumeration problem. As we know an unconditional lower bound on the total time of \(\Omega(n \log(n))\) and there are \(n\) partial solutions, we also know that the delay must be in \(\Omega(\log(n))\). As HeapSort initializes a MinHeap in \(\Theta(n)\) time and afterwards extracts the next smallest item from it in \(O(\log(n))\) time each, these lower bounds can be matched. Thus, comparison-based sorting can be done through homogeneous enumeration with HeapSort. Note that MergeSort for example is not sorting homogeneously, as it takes \(\Omega(n \log(n))\) time until the smallest object is known.