# Tag Info

22

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 sorting algorithms we actually care about. This means that measuring the number of comparisons or the number of steps taken gives you the same asymptotic running ...

9

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 indices, and then sort the original array in place with at most 1.5n moves. (That would actually be n/2 swaps; if a swap is cheaper than 3 moves then worst case is 4/...

6

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. That's why, in such cases, we do use those other operations for the analysis. For example: Binary insertion sort employs a binary search to determine the ...

5

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 since they ignore either the size of the first array or the lengths of the strings. Here are 2 different methods with their specific running times. The first of ...

2

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. order["three"] = 3. Then your comparator for sorting two objects a and b in the input is order[a] <= order[b] This way, you can easily abstract the pairwise comparisons. For example both Python and C++ (and probably many ...

2

Assuming the length of both arrays in your question is $\mathcal{O}(n)$, then in terms of required string comparisons: Create an array of the form inverse = [("one", 1), ("two", 2), ("three", 3)] where the additional indices are the array indices and sort it lexicographically on the first pair elements. This can be done in $\mathcal{O}(n \ln n)$ string ...

2

If a you are given a palindrome $p$ of size $N$ (as you say in the beginning of the question), then the longest palindrome is $p$ itself and you don't need to do any computation. If your input is not a palindrome but an arbitrary string, then you need to at least read the input and therefore $\Omega(N)$ is a trivial lower bound.

2

It seems like none of the other answers so far have mentioned a basic reason: There are many sorting algorithms whose total (asymptotic) time complexity is in fact bounded by the number of comparisons times the maximum time taken per comparison. Obviously that is why such sorting algorithms' cost should be measured by the number of comparisons, because they ...

2

Big Oh analysis is looking at the asymptotic behavior of an algorithm. In these analyses, the thing which gets done "more" will always overshadow the thing which gets done less. As an example, consider an algorithm which does $O(n)$ disk operations at a cost of 1,000,000,000 units each, and $O(n^3)$ comparisons at a cost of 1 unit each. Obviously for ...

1

Hi I make this post because this question is quite challenging for me and I want to know if my solution will pass "peer-review". Consider following algorithm for a RAM machine (// denotes integer division): algorithm ArrayMax Input: array $A$ of size $n$; $A[i] \in [1,2^m-1]$ Output: $max(A)$ left <- 1 right <- 1 max <- A[0] while right ...

1

1. Because you can avoid the other operations being expensive. Comparing integers is cheap. Comparing arbitrary elements of type T is typically as expensive as reading sizeof(T) bytes. Now, you might think "ok, but copying type-T elements is also expensive" - but we don't need to do that. We can just copy or move their indices in the input around and use ...

1

Just to summarize the answer above as a computer programme (the determinant method does not work): def atan2_lt( a, b, c, d ): """ Test atan2(a,b) < atan2(c,d) without computing either. """ if b*d < 0: return a < 0 if b < 0 else c > 0 elif b > 0 or a*c > 0: return a*d < b*c else: return a < 0 and c > 0 ...

1

Optimal to find best and second best is to build a binomial tree from the leaves up (i.e., compare disjoint pairs, compare the winners of pairs, and work your way up to the overall winner, always making sure to compare winners of groups of the same size). This ensures the second best is among those who lost to the winner, at most $\lceil \log_2 n \rceil$ ...

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