## 3 Algorithm I: Basic Algorithm
### Complexity Analysis  
Clearly, the complexity of the algorithm depends on the overall number of conflicts, the number of conflicts that require explicit symbol-wise comparisons, the number that can be resolved using earlier conflicts, and how much extra comparisons are required for those. We can notice that we require symbol-wise comparison mainly for the conflicts at the leftmost nodes on the conflict tree, and the first few conflicts in each node. For the sequence used in Figure 2 and Table 1, with \(n=16\), we have the following: 32 total number of conflict pairs; 20 can be resolved with only look-ups based on the neighbors (with no extra comparisons); 1 requires extra comparisons after lookup (a total of 6 extra comparisons); 11 cannot be resolved using lookups, and thus requires direct symbol-wise; comparisons (a total of 20 such comparisons in all). This gives 44 overall total comparisons, and 21 total lookups. This can be compared with the results for the worst case sequence with the same length, \(T=\texttt{a}^{16}=\texttt{aaaaaaaaaaaaaa}\). Here we obtain: 49 total number of conflict pairs; 37 can be resolved with only look-ups based on the neighbors (with no extra comparisons); 8 requires extra comparisons after lookup (a total of 12 extra comparisons); 4 cannot be resolved using lookups, and thus require direct symbol-wise; comparisons (a total of 19 such comparisons in all). This results in 41 overall total comparisons and 45 total lookups. While the total number of comparisons is similar for both cases, the number of lookups is significantly higher for \(T=a^{n}\), the worst case sequence. The following lemma establishes the total number of symbol comparisons and the number of conflicts that can be encountered using the algorithm. **Lemma 1:** Given an input sequence \(T=t_{0},t_{2}\ldots,t_{n-1}\), with length \(n\), the maximum number of symbol comparisons and the maximum number of conflict pairs are each in \(O(n\log n)\). _Proof._ Deciding on whether we can resolve a given conflict based on its neigbors requires only constant time, using Algorithm ResolveConflict(). Assume we are sorting the worst case sequence, \(T=a^{n}\). Consider level \(h\) in the conflict tree. First, we resolve the left-most conflict at this level, say conflict \(R_{L}\). This will require at most \(\frac{n}{2^{hmax-h}}=\frac{n}{2^{h}}\) symbol comparisons. For example, at \(h=h_{max}-1\), the level just before the lowest level, the leftmost conflict will be \(R_{1}=  
most \(\frac{n}{2^{hmax-h+1}}=2^{h-1}\) comparisons, plus constant time lookup using the earlier resolved neighbors. A similar analysis can be made for conflict pairs \(CP(i,j)\), where both \(i\) and \(j\) are odd. There are are at most \((\frac{n}{2^{h}}-1)\) conflicts for each node at level \(h\) of the tree. Thus, the total number of comparisons required to resolve all conflicts will be \(\sum_{i=0}^{\lceil\log n\rceil}2^{i}(\frac{n}{2^{i}}-1)\leq n\log n\). In the worst case, each node in the tree will have the maximum \((\frac{n}{2^{h}}-1)\) number of conflicts. Thus, similar to the overall number of comparisons, the worst case total number of conflicts will be in \(O(n\log n)\). \(\Box\)  
We state our complexity results in the following theorem:  
**Theorem 1:** Given an input sequence \(T=t_{0},t_{2}\ldots,t_{n-1}\), with symbols from an alphabet \(\Sigma\), Algorithm I solves the suffix sorting problem in \(O(n\log n)\) time and \(O(n)\) space, for both the average case and the worst case. _Proof._ The worst case result on required time follows from Lemma 1 above. Now consider the random string with symbols in \(\Sigma\) uniformly distributed. Here, the probablity of encountering one symbol is \(\frac{1}{|\Sigma|}\). Thus, the probability of matching two substrings from \(T\) will decrease rapidly as the length of the substrings increase. In fact, the probability of a conflict of length \(l_{k}\) will be \(Pr\{CP(i,j,l_{k})\}=\frac{1}{|\Sigma|^{2}l_{k}}\).