Video 6-6a: Addendum to §6.5 Suffix arrays

0:02 more importantly i want to point out that this this method fat pivot radix quicksort for sorting strings um it's a good method in the usual case but it does depend on the type of strings this precise statement that's made here that's from from the book from cedric and wayne that relies on an assumption about the strings in that case it's random strings where every character is randomly chosen from the allowable set of characters

0:37 if that is violated this is not true and in particular if if you apply it for suffix sorting and take a text that is just all a's and we will have this dollar at the end but that doesn't really make a big difference you can think about how this method would work it's maybe instructive to do this yourself but this is a really bad case in which in which you don't get this running time so this is a word of caution this method does work fairly well for the usual type of texts because they don't have to have the tend to have this degenerate characteristics but it's it's not true um i may may have given this impression yesterday that it always works in the worst case in n log n time this is not the case even if you randomize the pivots so i wanted to emphasize this again