Find largest palindromic substring, algorithm complexity

Question

You are given a string e.g. "acdfdcqqc" and need to create an algorithm to find the largest palindromic substring, in our case "cdfdc". It's easy to devise a O(n^2) algorithm by creating an array of size 2n and each time computing the length of the largest palindrome with that point for center i.e.:

a  -  c  -  d  -  f  -  d  -  c  -  q  -  q  -  c
1  0  1  0  1  0  5  0  1  0  1  0  1  4  1  0  1

For each of the 2n possible starting points I move in both direction finding the length of the largest palindrome starting at that position. So for each of the 2n operations I do at most O(n) operations, hence the O(n^2) time complexity.

I know it can be done in linear time using a fancier algo: https://en.wikipedia.org/wiki/Longest_palindromic_substring .

But assuming that the string we are handling are extracted from natural English text. If we pick a position at random in an English text, the expected symmetry that we might expect to find is quite low. I would even say that the expected symetry is of less than one character on each side. Therefore, is it ok for me to say that my algorithm is doing 2n times expected constant time operations, making the algorithm O(n) on average ?

Answer 1

The expected running time of an algorithm is the average running time of the algorithm over all possible inputs. (See Chapter 5 of CLRS.) As the textbook points out, it is not always easy to work this out, and sometimes it is useful to use an alternative: the running-time of the algorithm on a randomly-selected input. But the principle is the same: the notion of "expected running-time" is probabilistic, and only applies in aggregate to a large number of applications of the algorithm.

By contrast, the "worst-case running-time" is the worst running time of the algorithm on any input (of each length). That is also not always easy to compute, but it is amenable to least upper-bound computations, which are fine in the case of big-O notation because O(f(n)) only says that f(n) is an upper-bound.

If you apply an algorithm on a restricted set of inputs, you can specify either expected or worst-case running-time over that restricted set; if the inputs are not uniformly distributed over the range of possible inputs, you should take that into account when computed expected running time.

In the case of palindrome length, if the inputs are randomly-selected substrings of English text, the expected length of the largest palindrome will be (slightly) longer than the expected length of the largest palindrome of a text randomly selected from the entire universe of strings whose characters are drawn from the set of lower-case letters and the space character. But for both of these sets of inputs, the expected length of the longest palindrome is O(1).

So it is fine to say that your algorithm is "expected O(n)", although you should also specify the nature of the range of input strings. But if you cannot control the input to the algorithm, the worst-case running time is also relevant, since it is easy to craft a worst-case input for your naïve algorithm, and so a DoS attack on it is clearly feasible.

Answer 2

No.

In algorithm design, to say that an algorithm runs in expected O(n) time means that it does so for every possible input. That is, the expectation should be on the randomness of the algorithm (internal coin flips), not on the fact that the input is chosen uniformly at random from a restricted set.

However, it doesn't mean that your algorithm is not good. It is OK to use the fact that the input is restricted to English texts, hence possessing certain properties making the algorithm faster than on general inputs. But the terminology you're using (expected O(n) time) is reserved for algorithms whose running time is expected to be O(n) on every input.