The C++Course provides a general introduction to programming in C++. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details. 
Home Heap Overhead  
See also: Performance Analysis, Performance of Heaps  
Overhead
Performance analysis takes a lot of handwaving. First we ignored most of the operations the program performs and counted only comparisons. Then we decided to consider only worst case performance. During the analysis we took the liberty of rounding a few things off, and when we finished, we casually discarded the lowerorder terms.
How long that takes depends on the details of the implementation, including the additional work, besides the comparisons we counted, that each algorithm performs. This extra work is sometimes called overhead. It doesn't affect the performance analysis, but it does affect the run time of the algorithm. For example, our implementation of mergesort actually allocates subarrays before making the recursive calls and then lets them get garbage collected after they are merged. Looking again at the diagram of mergesort, we can see that the total amount of space that gets allocated is proportional to n log_{2} n, and the total number of objects that get allocated is about 2n. All that allocating takes time. Even so, it is most often true that a bad implementation of a good algorithm is better than a good implementation of a bad algorithm. The reason is that for large values of n the good algorithm is better and for small values of n it doesn't matter because both algorithms are good enough. As an exercise, write a program that prints values of 1000 n log_{2} n and n^{2} for a range of values of n. For what value of n are they equal?


Home Heap Overhead 