# Tag Info

## Hot answers tagged comparison

### Why do we use the number of compares to measure the time complexity when compare is quite cheap?

Sure. But in practice that is rare: the sorting algorithms we usually use or analyze in practice do at most a constant number of other operations per comparison, so this isn't an issue for the ...
• 145k

### Data structure or algorithm for quickly finding differences between strings

My solution is similar to j_random_hacker's but uses only a single hash set. I would create a hash set of strings. For each string in the input, add to the set $k$ strings. In each of these strings ...
• 159
Accepted

### Data structure or algorithm for quickly finding differences between strings

It's possible to achieve $O(nk \log k)$ worst-case running time. Let's start simple. If you care about an easy to implement solution that will be efficient on many inputs, but not all, here is a ...
• 145k

### Why do we use the number of compares to measure the time complexity when compare is quite cheap?

If moving an item were n times more expensive than comparing, selection sort would suddenly be the most efficient algorithm. But if moving an item were expensive, we could sort an array of array ...
• 25.9k

### Data structure or algorithm for quickly finding differences between strings

I would make $k$ hashtables $H_1, \dots, H_k$, each of which has a $(k-1)$-length string as the key and a list of numbers (string IDs) as the value. The hashtable $H_i$ will contain all strings ...
• 5,194

### How do I find the max and min value of an array in 3n/2−2 comparisons?

Imagine having a tournament made of the array elements. Group the array elements into pairs, then compare each pair. Put the larger numbers into one group and the smallers number into another group. ...
• 8,947

### Why do we use the number of compares to measure the time complexity when compare is quite cheap?

what if the number of comparisons can be O(n log n) or O(n), but then, other operations had to be O(n²) or O(n log n), then wouldn't the higher O() still override the number of comparisons? Um, yeah. ...
• 446
Accepted

Accepted

### prove that minimal number of comparisons to find median among five elements is 5

Your proof is correct. But I don't think 5 comparisons is achievable. Here is the algorithm that finds the median in 6 comparisons. Sort the first two pairs. [ 2 comparisons] Order the pairs w.r.t. ...
• 728
Accepted

### sort n numbers in the range [0,1] without multiplying or dividing

The $\Omega(n \log n)$ lower bound still applies; you still can't do better than $O(n \log n)$. (Proof: Take any array of numbers. You can find the maximum and minimum in $O(n)$ time. Then, rescale ...
• 145k
Accepted

### Are comparison sort algos appropriate for SUBJECTIVE sorting?

I suggest reading about the theory on rating systems and ranking systems. There are many standard algorithms and methods for this. I would recommend reading the following resources, to get you ...
• 145k

### Why is finding minimum number of comparisons to sort $n$ elements so difficult?

Let's say the size of the array is such that there are $2^{k-1} < x ≤ 2^k$ possible permutations, so the theoretical lower bound to sort this array is k comparisons. Any comparison divides the ...
• 25.9k
Accepted

### Turing machine - compare two words

Yes, running back and forth comparing letters is the best you can do. You could always read and remember two, three or any fixed amount of symbols at a time; then there would be less running back and ...

### Algorithm to compare two data sets

I think you are asking about how to implement a set difference operation. Specifically, if user 1's recipe for salad 1 is viewed as a set of ingredients A, and user 2's recipe for salad 1 is viewed as ...
• 1,229

### Application of cosine similarity to detect plagiarism

Usually this would be used in conjunction with a bag of words model. You need to convert each document to a vector where the length of the vector is the number of words in the vocabulary. The entries ...
• 522
Accepted

### Compare vs Radix

In theory sorting a long sequence of int should be a prime candidate for radix sort as it grows linear in the number of elements to be sorted, while any comparison based sorting algorithm can't be ...
• 217

### Fast comparison with a tolerance

As others have said, what you want is impossible. But you might want to look at locality-sensitive hashing. It achieves something vaguely similar: if two elements are similar, then with significant ...
• 145k

### Fast comparison with a tolerance

The second variant isn't much better: $\forall s,r: |r-s| < 1 \Rightarrow K(r) = L(s)$ implies that $\forall r: K(r) = L(r)$, as $r = s$ is only a special case. On the other hand, you are down to ...
• 51