An asymptotic expression typically contains exact terms and O-terms, for example n3 + 2n2 + O(n). The basic framework for this asymptotic ring is already implemented. The main aim of this summer of code project is to extend its functionality up to the point where asymptotic expressions with explicit constants are fully supported. In his book, “Asymptotic Methods in Analysis” on page 5, deBruijn calls it an “L-term”, but we will call it “B-term”. B_{20}(3z) is a B-term, which stands for an expression which is bounded in absolute value by 3|z| for |z| ≥ 20. Sometimes, in research, it is important to know from which values of the variable on the asymptotic expression has enough precision to decide wether it is larger than a given bound. This cannot be achieved by O-terms (because the unknown implicit constant might be very large). For example, the average number of comparisons of classical quicksort is 2n log n + O(n). When comparing with recent variants, such as dual pivot quicksort with average number of comparisons 1.8n log n + O(n), it is interesting to know how large the O-terms are in order to know when dual-pivot quicksort will be more efficient than classical quicksort.



Thomas Hagelmayer


  • Benjamin Hackl
  • Clemens Heuberger