Improved Average Complexity for ComparisonBased Sorting. This paper studies the average complexity on the number of comparisons for sorting algorithms. Its informationtheoretic lower bound is (n lg n  1.4427n  O(log n)). For many efficient algorithms, the first (nlg n) term is easy to achieve and our focus is on the (negative) constant factor of the linear term. The current best value is (1.3999) for the MergeInsertion sort. Our new value is (1.4106), narrowing the gap by some (25%). An important building block of our algorithm is xe2x80x9ctwoelement insertion,xe2x80x9d which inserts two numbers A and B, (Au003cB), into a sorted sequence T. This insertion algorithm is still sufficiently simple for rigorous mathematical analysis and works well for a certain range of the length of T for which the simple binary insertion does not, thus allowing us to take a complementary approach with the binary insertion.

New and Improved Algorithms for Unordered Tree Inclusion The tree inclusion problem is, given two nodelabeled trees P and T (the pattern tree and the text tree), to locate every minimal subtree in T (if any) that can be obtained by applying a sequence of node insertion operations to P. Although the ordered tree inclusion problem is solvable in polynomial time, the unordered tree inclusion problem is NPhard. The currently fastest algorithm for the latter is from 1995 and runs in O(poly(m,n) * 22d)  O*(22d) time, where m and n are the sizes of the pattern and text trees, respectively, and d is the maximum outdegree of the pattern tree. Here, we develop a new algorithm that improves the exponent 2d to d by considering a particular type of ancestordescendant relationships and applying dynamic programming, thus reducing the time complexity to O*(2d). We then study restricted variants of the unordered tree inclusion problem where the number of occurrences of different node labels andor the input treesu0027 heights are bounded. We show that although the problem remains NPhard in many such cases, it can be solved in polynomial time for c  2 and in O*(1.8d) time for c  3 if the leaves of P are distinctly labeled and each label occurs at most c times in T. We also present a randomized O*(1.883d)time algorithm for the case that the heights of P and T are one and two, respectively.