## 3 Analyses  
Obviously, the problem of generating 2D lattice \(L(n_{1},\,n_{2})\) paths according to a given number of _turns_ is more challenging than a simple multiset permutation problem. This is because, for a simple multiset permutation algorithm, to generate permutations with a given number of _turns_, it requires both a time to generate all permutations and a time to perform additional comparisons and calculations to pick out those permutations with a given number of _turns_. Furthermore, if we want generate all paths in a specified order of _turns_, for example a decreasing or an increasing, we must spend additional time to sort them according to the number of _turns_ they have. Not surprisingly, we can easily prove the following theorem. **Theorem 2. ** The time complexity of a simple multiset permutation algorithm for generating two-item \(\{\mathrm{A}^{n_{1}},\,\mathrm{B}^{n_{2}}\}\) multiset permutations according to a given number of _turns_ is \(O(\frac{n^{n+1.5}}{n_{1}^{n_{1}+0.5}\times n_{2}^{n_{2}+0.5}})\), here \(n=n_{1}+n_{2}\) ; and in case of \(n_{1}=n_{2}\)  the time complexity is \(O(n^{0.5}2^{n+1})\). **Proof**. For a two-item multiset permutation, there are totally \(\frac{n!}{n_{1}!n_{2}! }\) permutations, and each one needs \(n-1\) comparisons to calculate how many _turns_ it has. It is well known that the factorial function is exponential growth. By using the _Stirling approximation_, \(n!=\sqrt{2\pi n}\!\left(\frac{n}{e}\right)^{n}\), we have:  
\[\frac{n!}{n_{1}!n_{2}!}=\frac{\sqrt{2\pi n}\!\left(\frac{n}{e}\right)^{n}}{ \sqrt{2\pi n_{1}\!\left(\frac{n_{1}}{e}\right)^{n}}\sqrt{2\pi n_{2}\!\left( \frac{n_{2}}{e}\right)^{n_{2}}}}=\sqrt{\frac{1}{2\pi}\,n_{1}^{n+0.5}\times n _{2}^{n_{2}+0.5}}\,,\]  
then after multiplying the term by \(n-1\) we have \(O(\frac{n^{n+1.5}}{n_{1}^{n_{1}+0.5}\times n_{2}^{n_{2}+0.5}})\). Moreover, in the case of \(n_{1}=n_{2}\) the time complexity is \(O(n^{0.5}2^{n+1})\). In other words, the running time is exponential growth on the problem size \(n\). \(\Box\)Fortunately, the proposed Algorithm **G2 DLP** significantly reduces this time complexity to a linear order. Now, let us analyze the complexity of three components of Algorithm **G2 DLP** individually. Since the amendments and additions to Algorithms H and L have little influence in time complexity, we can directly use the time complexity of Algorithms H and L, respectively, to stand for the time complexity of Algorithms **Partition** and **Permute**. First, if we let \( \begin{vmatrix}n\\ m\end{vmatrix} \) denote the number of partitions of \(n\) that have exactly \(m\) parts, then the running time per partition of Algorithm **Partition** is \( \begin{vmatrix}n\\ m\end{vmatrix} \). By [PERSON] [18] (p. 39), we know that the total running time of Algorithm H is at most a small constant multiplied by the number of partitions visited, plus \(O(m)\). The key quantity is the value of \(j\), in H4, the smallest subscript for which \(a_{j}<a_{1}-1\). Let \(c_{m}(n)\) be the accumulated total value of \(j-1\) summed over all of the \( \begin{vmatrix}n\\ m\end{vmatrix} \) partitions generated by Algorithm H. [PERSON] [18] (p. 50) has proved that the cost measure \(c_{m}(n)\) for Algorithm H is at most \( \begin{vmatrix}n\\ m\end{vmatrix} +m\). Regard \(c_{m}(n)\)\( \begin{vmatrix}n\\ m\end{vmatrix} \) as a good indicator of the running time per partition, therefore, the running time per partition of Algorithm H is \( \begin{vmatrix}3+m\end{vmatrix} \)\( \begin{vmatrix}n\\ m\end{vmatrix} \). Second, with regard to the Algorithm **Permute**, the running time is reasonably efficient [1] (p. 40). When the partition produced by Algorithm H is simply a set containing distinct elements, for example 5321 as a partition of partitioning integer 11 into 4 parts, the means of the number of comparisons by step L2 and step L3 are about 1.718 and 1.359, respectively [1] (pp. 101-102); and the average number of interchanges in step L4 is about 0.543 [1] (p. 102).