Can we do it better than O(n^2) ? : algorithms

Can we do it better than O(n^2) ? : algorithms

Do you want to prove that the number of insertions can be o(n² ), or that the worst-case time to compute the minimum number of insertions is o(n² )? (Yes, those are both little ohs.)

The first question is easy; just insert the reversal of the entire string, except its first character, before the first character. That's exactly n-1 insertions. Moreover, those insertions can be computed in O(n) time. Moremoreoverover, if the characters in your input string are all distinct, n-1 insertions is the best you can possibly hope for.

The second question is much harder, but without additional assumptions, the answer is essentially NO. Some additional assumptions that might help:

• The minimum number of insertions is at most k, for some k = o(n).
• The minimum number of insertions is at least n-k, for some k = o(n).

Even when the answer is about n/2, you can shave a log factor or two from the running time using the "Four Russians" technique, but this is a much more advanced technique than you'd normally see in an undergrad algorithms class.

Unlike simple problems like comparison-based sorting, we don't know how to prove lower bounds for this kind of problem. In principle, there could be an algorithm that runs in, say, O(n^3/2 ) time, but that would be a truly spectacular result — not just publishable, but revolutionary.

tl;dr: Unless you are an algorithms researcher, you can reasonably assume that the problem cannot be solved in subquadratic time.

Read full article from Can we do it better than O(n^2) ? : algorithms