Questions tagged [comparison]
The comparison tag has no usage guidance.
46
questions
0
votes
1answer
24 views
Longest palindrome substring in logarithmic runtime complexity
In a palindrome of size N, the amount of candidates for the longest palindrome is N^2. Therefore, the information theoretic lower bound (IBT) should be lg(N^2), which is equivalent to a runtime ...
20
votes
7answers
3k views
Why do we use the number of compares to measure the time complexity when compare is quite cheap?
I think one reason a compare is regarded as quite costly is due to the historical research as remarked by Knuth, that it came from tennis match trying to find the second or third best tennis player ...
0
votes
0answers
22 views
Difference between GA and ABC for inference
If I have an agent-based model and I want to infer the parameters, I would normally used ABC (approximate bayesian computation), but I was recently working with someone who was using GA (genetic ...
3
votes
3answers
173 views
Sorting array of strings (with repetitions) according to a given ordering
We get two arrays:
ordering = ["one", "two", "three"]
and
...
0
votes
0answers
19 views
Comparison tree to get a minimum number of comparisons for merging sorted lists
Suppose A is a sorted list of length n and B is a sorted list of length 2. I am asked to ...
-1
votes
1answer
135 views
Recurrence Relation of Ternary search and the number of comparisons with binary search
i was reading the binary search and ternary search algorithms. But i had a doubt with recurrence relation of ternary search as somewhere it is T(n/3)+c and T(2*n/3)+c. I want to know which one is ...
3
votes
1answer
241 views
Minimum number of comparision to find the third largest element in an array of distinct integers?
For the second largest element, I know that the formula is $n+ \lceil\log n \rceil -2 $
Is there any formula for the third largest element? and if so, what is the derivation?
0
votes
0answers
29 views
Algorithm for comparing object dates and types
I'm looking for a good / efficient algorithm to compare classes of driver licences (or any type of similar objects) and their dates, so that they do not overlap and come in certain order.
eg. We have ...
2
votes
0answers
70 views
Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks
I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
1
vote
0answers
31 views
How to justify using available code (in different language) for comparing algorithms [closed]
I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm in the literature. Our algorithm is in MATLAB, and ...
1
vote
1answer
470 views
Turing machine - compare two words
I have a simple turing machine with single tape.
I need to compare two words <w1>$<w2>$ and write output.
Language is all letters and numbers.
I did ...
3
votes
1answer
90 views
Why is finding minimum number of comparisons to sort $n$ elements so difficult?
In The Art of Computer Programming 2nd Ed, Vol 3, Section 5.3.1 then discuss a function $S(n)$ which is define as:
$S(n)$ : The minimum number of comparisons that suffice to sort $n$ elements.
...
3
votes
1answer
34 views
Finding maximum takes at least $\lceil n/2 \rceil$ comparisons
We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$.
I want to prove that finding the maximum in $A$ (that is, outputting the index ...
3
votes
1answer
75 views
Are comparison sort algos appropriate for SUBJECTIVE sorting?
I've been tasked with creating an online feature that ranks 50 fantasy characters from a variety of domains based on combat acumen and polls users one which one is the most powerful based on their ...
1
vote
1answer
54 views
An algorithm to drop low-priority items from a heap-based priority queue
I am looking for an efficient algorithm to drop from a complete binary min heap all items whose weight exceeds a given value. (Or, equivalently, to drop from a priority queue realised by such a heap ...
1
vote
1answer
479 views
Sorting lower bounds for almost sorted array
Can't find a good way to tackle the problem. Would appreciate any help.
$A$ is an $n$ items array from an ordered set, in which every item is at most
$\log n $ indices away from its position in the ...
3
votes
1answer
215 views
d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions
Let's say that Dijkstraās algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$.
Then for a ...
1
vote
1answer
64 views
Optimize sorting matrix entries by row and column
I am writing a routine to store an $M$-by-$N$ sparse matrix in a balanced binary tree. The insertion routine calls a comparison function to determine where a new matrix entry $(i,j)$ should be ...
0
votes
1answer
1k views
How to compare an element with other elements within an array efficiently for a condition
I need to compare each index with one another and associated array value as well.
For example,
...
3
votes
2answers
57 views
sort n numbers in the range [0,1] without multiplying or dividing
Given an array with n real numbers, each in the range [0,1], I need to sort them. Moreover, the only operations that are allowed are comparisons or copying.
It means I cannot multiply or divide the ...
1
vote
0answers
40 views
Merge unstructured with structured data
We have a database with well-formated and structured data. From time to time we get Excel - files from our clients. This Excel Files have to be imported to the database. It it very important that we ...
19
votes
12answers
10k views
Data structure or algorithm for quickly finding differences between strings
I have an array of 100,000 strings, all of length $k$. I want to compare each string to every other string to see if any two strings differ by 1 character. Right now, as I add each string to the ...
1
vote
2answers
93 views
What is the name for the comparison used in C's memcmp?
The C memcmp function (and strcmp) does a comparison similar to the function below for comparing integers:
...
2
votes
2answers
64 views
Compare two atan2
I tried to implement points location algorithm using Fortune's algorithm to get Voronoi diagram and another sweepline algorithm to locate many points in $O(n\cdot\log(n))$. If there are multiple ...
1
vote
3answers
598 views
finding best n players in minimum number of comparisons
I am trying to find out if there is any generic way to find out first to nth best player in a tournament if n is less than the square root of input size i.e. 5 best players in the sample size of 25 ...
3
votes
0answers
768 views
How to determine the fewest number of comparisons for Heapsort?
I'm currently doing an exercise that asks to prove that Standard-Heapsort requires at fewest $\frac{1}{8} n \log(n) - O(n)$ comparisons, in its best case.
In its average case, Heapsort only requires $...
2
votes
2answers
1k views
Proving at least $n-1$ comparisons are needed to test if an array is sorted
so I need to prove the following:
Prove that $n-1$ comparisons are sometimes necessary to test whether an array with $n$ distinct elements is sorted in increasing order, for any $n \geq 1$.
The ...
1
vote
1answer
378 views
Identify similar functions
I was wondering if there is any technique in order to recognize similar functions behaviour. In particular, suppose that I implement two functions $f$ and $g$ in a certain programming language $P$ and ...
4
votes
1answer
590 views
Median-of-medians in O(log n) memory
Is there a way to use median-of-medians to find a median in,
simultaneously, ā āO(log n) ā āmemory and O(n) comparisons?
The user orlp on this site seems to claim that there is.
Getting ā āO(log n) ...
4
votes
2answers
287 views
Is there a metric for the similarity of two image filters?
Definitions
An image filter is a matrix $m \in \mathbb{R}^{k_1 \times k_2 \times k_3}$ which gets applied to an image $I \in \mathbb{R}^{l_1 \times l_2 \times l_3}$ as a discrete convolution
$$I'(...
0
votes
1answer
205 views
Comparing 2 video files [closed]
I have a bunch of wmv files (~300), named the following way: video1.wmv -> videox.wmv. Some of these video files, are exact ...
0
votes
1answer
115 views
Sorting algorithm which sorts half the possible inputs in linear time
Prove that there isn't any comparison sort algorithm which for an input of size $n$ can sort at least half of the permutations of the input in linear time.
(For the other half the algorithm can ...
1
vote
1answer
203 views
How to compare two objects for percentage of equivalence
I'm trying to create a nodeJS application. It allows users to rate a bunch of songs and it stores them in their user profiles. I use this information to compare them to other users, and try to find ...
0
votes
2answers
202 views
How to determine(with some confidence) if two extremely long lists of numbers (terabytes) are similar?
I have two very large files with numbers seperated by commas. What is most efficient/fastest way to say with some confidence that these two files have same numbers.
The main rule if if two ...
5
votes
3answers
7k views
How do I find the max and min value of an array in 3n/2ā2 comparisons?
So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers ...
1
vote
0answers
532 views
Text data comparison
Okay lets say i have two data structures . two phone data for example containing their Name and spec ( cpu , ram , display etc ) . I want to check if these two phones are the same or not . Their names ...
2
votes
3answers
85 views
Fast comparison with a tolerance
I am trying to find a way to compare two real numbers (actually floating-point) with a tolerance, i.e. test $|r-s|\le\epsilon$. Without loss of generality, $\epsilon=1$.
I want to do this by ...
0
votes
1answer
52 views
prove sufficient number of comparisons for the merge problem
It is given two subsequences. Their length are following: $2$ and $5$.
I can show that lower bound of comparisons is $5$. My problem is that I can't show that $5$ is sufficient number of comparisons ...
0
votes
2answers
4k views
prove that minimal number of comparisons to find median among five elements is 5 [closed]
I would like to prove that we need at least five comparisons to find median amoung five numbers.
And my proposition:
Let's consider tree of comparisons. There are at least $5 \cdot {4\choose 2} = 30$ ...
0
votes
1answer
197 views
Compare vs Radix
Is it better to use comparison or radix sort to sort a long sequences of java int array?
I know that I should probably use mergesort (NlogN) for comparison sort, since it is one of the fastest and ...
1
vote
1answer
283 views
comparison in speed between the processor and the hard disk
I'm reading through William Stalling's operating system intrnals and design principles book. Talking about interrupts, it gives the following examples when comparing the speed of a processor and a ...
0
votes
0answers
1k views
Pseudocode for checking if two arrays contain the same elements?
I'm not so much confused as to write the actual code as I am to write the pseudocode.
To determine if two arrays of the same size contain the same elements, I know you would need two for loops, then ...
2
votes
2answers
2k views
Application of cosine similarity to detect plagiarism
Can anyone tell me how using cosine similarity to see the correlation between two documents actually shows you if someone is plagiarising the other? I understand how cosine similarity works but don't ...
2
votes
2answers
117 views
Why comparison is dominant time consumption for comparison-based sorting algorithms? [duplicate]
Comparison-based sorting algorithms does a number of different operations to accomplish the sorting, why comparisons are the dominant time consumption? While I understand the standard analyses of ...
3
votes
1answer
888 views
Cost of partitioning in quicksort
I'm reading "Algorithms Fourth Edition" by Sedgewick & Wayne and am wondering if I have spotted an error in the book or if I just can't wrap my head around something so simple.
When talking about ...
6
votes
2answers
2k views
More efficient algorithm for determining if one list is a sublist of another list
I'm trying to build an algorithm which takes two lists of natural numbers and finds if every element of the first list is displayed at least once in the second list.
What if the list is sorted?
An ...
