Skip to main content
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 ...
D.W.'s user avatar
  • 161k
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 ...
Simon Prins's user avatar
13 votes

Find 1s in almost all 0 array using comparisons only

Start by splitting the 100 elements in 50 pairs of two, and use a comparison on each pair. If a comparison returns -1 or 1, then you've found one of the elements which is 1 (and the other one must be ...
orlp's user avatar
  • 13.6k
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 ...
D.W.'s user avatar
  • 161k
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 ...
gnasher729's user avatar
  • 30.5k
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 ...
j_random_hacker's user avatar
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. ...
Kelly Bundy's user avatar
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 $...
Yuval Filmus's user avatar
4 votes
Accepted

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 ...
Narek Bojikian's user avatar
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 ...
Steven's user avatar
  • 29.5k
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 ...
D.W.'s user avatar
  • 161k
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 ...
D.W.'s user avatar
  • 161k
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. ...
KWillets's user avatar
  • 1,274
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}...
Simon Kohl's user avatar
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 ...
hengxin's user avatar
  • 9,561
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 ...
D.W.'s user avatar
  • 161k
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 ...
gnasher729's user avatar
  • 30.5k
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 ...
Peter Leupold's user avatar
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 ...
Daniel Wagner's user avatar
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 $...
D.W.'s user avatar
  • 161k
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 ...
D.W.'s user avatar
  • 161k
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/...
Yuval Filmus's user avatar
2 votes

Data structure or algorithm for quickly finding differences between strings

Here is a more robust hashtable approach than the polynomial-hash method. First generate $k$ random positive integers $r_{1..k}$ that are coprime to the hashtable size $M$. Namely, $0 \le r_i < M$. ...
user21820's user avatar
  • 727
2 votes
Accepted

How to compare an element with other elements within an array efficiently for a condition

In the general form you present, you have $\Theta(n^2)$ things to compare so you need $\Omega(n^2)$ time. If you know more about the arrays or the comparison operator (e.g., the arrays are sorted and ...
David Richerby's user avatar
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 ...
D.W.'s user avatar
  • 161k
2 votes

Data structure or algorithm for quickly finding differences between strings

A lot of the algorithms posted here use quite a bit of space on hash tables. Here's an $O(1)$ auxiliary storage $O((n \lg n) \cdot k^2)$ runtime simple algorithm. The trick is to use $C_k(a, b)$, ...
orlp's user avatar
  • 13.6k
2 votes

An algorithm to drop low-priority items from a heap-based priority queue

Let $n$ denote the size of the min-heap. It's easy to do this in linear time, i.e., $O(n)$ time: walk through the heap, copying over only the items that are below the threshold into an array; then ...
D.W.'s user avatar
  • 161k
2 votes
Accepted

Finding maximum takes at least $\lceil n/2 \rceil$ comparisons

In fact, at least $n-1$ comparisons are needed. Indeed, consider the graph on the vertex set $A$ whose edges correspond to pairs of elements which were compared. If less than $n-1$ comparisons were ...
Yuval Filmus's user avatar
2 votes

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

I think a straightforward way to accomplish this would be to create a mapping of every element in your ordering list to its index i.e. ...
Throckmorton's user avatar

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