# Tag Info

### 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 ...
• 161k

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

### 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 ...
• 13.6k
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 ...
• 161k

### 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 ...
• 30.5k

### 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,479

### 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. ...
• 480
Accepted

### 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,561

### 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 ...
• 161k

### 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 ...
• 30.5k
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,268
Accepted

• 278k

### 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$. ...
• 727
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 ...
• 81.9k
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 ...
• 161k

### 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)$, ...
• 13.6k

### 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 ...
• 161k
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 ...
• 278k