What is the runtime for determining, through a naïve binary search, whether a string of length m is found in a suffix array of a string of length n?
The runtime for a naïve binary search on a suffix array of a string of length n to determine whether a string of length m is present would be O(mlogn).
The runtime for determining whether a string of length m is found in a suffix array of a string of length n using a naïve binary search is O(m * log(n)), where m is the length of the string being searched for and n is the length of the suffix array.
In a naïve binary search approach, the algorithm repeatedly divides the search space in half until the desired string is found or determined to not exist. The search space is initially the entire suffix array, and at each step, the algorithm compares the desired string with the middle element of the current search space. Based on the comparison, the algorithm either continues searching in the left or right half of the search space.
The log(n) term comes from the fact that the search space gets halved with each comparison, and it takes log(n) comparisons to reduce the search space to a single element.
For each comparison, the algorithm needs to compare each character of the desired string with the corresponding character of the current middle element. Since the length of the desired string is m, it takes O(m) time for each comparison.
Therefore, the overall runtime of the algorithm is O(m * log(n)).