22 votes

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
15 votes

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 ...
12 votes
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
9 votes

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
7 votes

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 ...
7 votes

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. ...
6 votes

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. ...
5 votes
Accepted

Sorting lower bounds for almost sorted array

Suppose that every element is at most $k$ elements away from its true position. In order to sort the array, you maintain a heap. At step $i$, you add $A_i$ to the heap, and pop the minimum element as $...
5 votes

Sorting array of strings (with repetitions) according to a given ordering

The other answers provide correct solutions. However, you can do a bit better considering multivariate complexity. Note that the provided running times in the other answers are not quite specific ...
4 votes

Fast comparison with a tolerance

If for all $|r - s| < 1$ it is the case that $K(r) = K(s)$ then $K$ is constant (exercise). What you are asking is impossible. One thing which is possible is to compare keys with three rather ...
4 votes
Accepted

prove sufficient number of comparisons for the merge problem

You asked about what approach to take, so I'll explain the general approach to take for this kind of problem. The way to prove that 5 comparisons are sufficient is to exhibit a specific algorithm for ...
  • 145k
4 votes
Accepted

Sorting an array with x sorted subarrays

In the first exercise you have to merge a constant number of subarrays, i.e., $3$. In the second exercise you'd have to merge $\Theta(n)$ subarrays, each of constant size. If you were able to produce ...
  • 24.5k
3 votes
Accepted

What is the name for the comparison used in C's memcmp?

The question is about a three-valued function in a situation where a boolean is often used (eg <=). I personally refer to this as the sign or signum: the sign of the difference of the comparands. ...
  • 1,254
3 votes

Proving at least $n-1$ comparisons are needed to test if an array is sorted

You can use a simple adversary argument (in Jeff's lecture note) to prove that every correct algorithm has to compare $a_i$ with $a_{i+1}$ for $i=0,1, \ldots, n−2$. If it is not the case, you can ...
  • 9,259
3 votes

Identify similar functions

The problem is not decidable (by reduction from the Halting problem), so there is no perfect algorithm that always terminates and always gives the correct answer. Therefore, you'll need to make some ...
  • 145k
3 votes
Accepted

Is there a metric for the similarity of two image filters?

The ‘k-translation correlation’ is probably a good candidate for what you are looking for. It measures the maximum correlation between a pair of two filters $\mathbf{W_i}$ and $\mathbf{W_j}...
3 votes
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. ...
3 votes
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
3 votes
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
3 votes

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
3 votes
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 ...
3 votes

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 ...
2 votes

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
2 votes
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
2 votes

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
2 votes

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 ...
2 votes
Accepted

How to compare two objects for percentage of equivalence

One approach is to use low-rank matrix factorization to approximate the ratings matrix, then use a nearest neighbors data structure. In particular, let $M$ be the $m \times n$ ratings matrix, where $...
  • 145k
2 votes
Accepted

Comparing 2 video files

A general algorithm is to compute the SHA256 hash of each file, then sort the hashes and look for duplicates. After sorting any duplicates that may exist will be consecutive. For all practical ...
  • 145k
2 votes
Accepted

finding best n players in minimum number of comparisons

You can't. There isn't enough information in a single elimination tournament to know who the $n$ best players are. All you can infer is who the best player is. You can't even tell who is second ...
  • 145k
2 votes

Compare two atan2

The following answer is based on the following graph, taken from Wikipedia: If $x_i,x_j > 0$ then you can use the monotonicity of the arctangent to get the equivalent condition $y_i/x_i < y_j/...

Only top scored, non community-wiki answers of a minimum length are eligible