We’re rewarding the question askers & reputations are being recalculated! Read more.

# Tag Info

1

I am going to prove that a special case of this problem is NP-hard and hence we can not aim for a polynomial time algorithm for the general case (unless P=NP). Assuming each word has length exactly 1. This means each word is only one letter and each sentence is a combination of letters. We are looking now for a set of at most $k$ letter that construct as ...

2

I shall modify the question a bit and answer the following version, which I think is more correct: Prove that the lower bound of any character-comparing string sorting algorithm is $\Omega(d + n \log n)$, where $d$ is the sum of the lengths of the distinguishing prefixes of all the strings in our set $S$ and $n$ is the cardinality of the strings set $S$. ...

2

The time complexity you indicated is the lower bound of your specific problem. A lower bound is the worst-case running time of the most optimized TM that recognizes membership in the language. Lover bound for sorting algorithms is $\Omega(n \log n)$ this means that it is not possible to do better than this and all the sorting cases (instances) may have a ...

Top 50 recent answers are included