All Questions
2 questions
6
votes
1
answer
287
views
Counting number of swaps to make two strings equal in linear time
The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant.
...
- 163
2
votes
1
answer
2k
views
Can we count the number of inversions in time $\mathcal{O}(n)$?
It is possible to find the total number of inversions by $\mathcal{O}(n\log{}n)$ running time (extension of merge-sort algorithm for example).
Is there more asymptotically efficient way to do it? $\...
- 215