3 ms·

> Complexity theory tells us you can sort those in nlogn time. You seem to be attacking a strawman — no CS textbook says you can sort n strings in O(n log n) t

by svat 3y ago

> Complexity theory tells us you can sort those in nlogn time. You seem to be attacking a strawman — no CS textbook says you can sort n strings in O(n log n) time (that's just the number of comparisons); of course sorting n strings each of length m will take O(mn log n) time — that is, you have to multiply by the average time for each comparison. This is what complexity theory says, and what any good textbook would also say. You don't need "a new complexity theory built on top of Information Theory"; the current one already does so. (And m could be much bigger than log n too.)

hinkley 3y ago
I’ve seen actual implementations of hash tables claim O(1) amortized insertion time, not O(m). And I misspent a summer about 5 years back thinking I had a constant space overhead mergesort (when what I had was poorly chosen input data. Bummer). I read a lot of mergesort papers then. Nobody mentioned m. I may get bored and check your theory on textbooks, but I suspect you’re letting optimism get the better of you. In a conversation about pragmatism that’s not good. All of my examples at the top were not hypothetical, they were all actual arguments I’ve had with real people or documentation I bitched to someone about. Edit: I mean fuck, even Wikipedia has it wrong: > In sorting n objects, merge sort has an average and worst-case performance of O(n log n). N objects. Not n numbers. If you want to fix the world instead of declaring bankruptcy with me, start there. At least they get space overhead right farther down: > In this case, the notion of "in-place" can be relaxed to mean "taking logarithmic stack space", because standard merge sort requires that amount of space for its own stack usage.
- svat 3y ago
  Well, Wikipedia is obviously wrong there. I've fixed it to say number of comparison operations: https://en.wikipedia.org/w/index.php?title=Merge_sort&diff=prev&oldid=1185699028 https://en.wikipedia.org/w/index.php?title=Merge_sort&diff=p... Note also that in computational complexity theory, "n" is the length of the input in bits: if you have k strings each of length l, using a regular sort, with a comparison subroutine that takes O(l) time, will take O(kl log k) time — O(k log k) operations each taking O(l) time — which, as n=kl, is O(n log k), upper-bounded by O(n log n). ———— I looked up a couple of influential algorithms textbooks in the meantime, and I must admit this is less clear than I'd have liked (though complexity theorists are very aware of it). • TAOCP vol 3 (which starts with Chapter 5, Sorting) says, on page 5 (in the introduction section of the chapter, where he often says things informally and not exactly): > The time required to sort N records, using a decent general-purpose sorting algorithm, is roughly proportional to NlogN; we make about logN “passes” over the data. This is the minimum possible time, as we shall see in Section 5.3.1, if the records are in random order and if sorting is done by pairwise comparisons of keys. Thus if we double the number of records, it will take a little more than twice as long to sort them, all other things being equal. (Actually, as N approaches infinity, a better indication of the time needed to sort is N(logN)^2, if the keys are distinct, since the size of the keys must grow at least as fast as logN; but for practical purposes, N never really approaches infinity.) It's emphasized less than I'd have liked but he has already mentioned your observation though (and I checked this was present in the first edition in 1973). BTW, note no "O" here: where possible he actually gives the number of machine operations, including the constant factor. TAOCP is very much a "nothing up my sleeve" book, where everything is analyzed down to the constants (where possible) and machine code given. He starts with a very concrete problem where what's being sorted are numbers that each fit in a machine word: > “Memory locations R+1, R+2, R+3, R+4, and R+5 contain five numbers. Write a computer program that rearranges these numbers, if necessary, so that they are in ascending order.” and he makes it clear that what's being sorted are records that contain keys and satellite information, and he's going to mostly assume the keys are integers that fit in a word, sometimes even part of a word. The mention of sorting strings (can get there via the index) is an exercise on page 178: > Design an algorithm to sort strings α1, ..., αn on an m-letter alphabet into lexicographic order. The total running time of your algorithm should be O(m+n+N), where N = |α1| + · · · + |αn| is the total length of all the strings. Note that this running time is better than O(n (N/n) log n) — assuming that the strings are of about equal length N/n, and using a standard sorting algorithm — that I mentioned above. The solution is essentially to construct a trie. • CLRS starts its sorting section with "A sequence of n numbers" and has: > A sorting algorithm describes the method by which we determine the sorted order, regardless of whether we are sorting individual numbers or large records containing many bytes of satellite data. Thus, when focusing on the problem of sorting, we typically assume that the input consists only of numbers. Translating an algorithm for sorting numbers into a program for sorting records… Its index on sorting variable-length items points to p206 (in the 3rd edition) where, similar to TAOCP: > 8-3 Sorting variable-length items > a. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is n. Show how to sort the array in O(n) time. > b. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. Show how to sort the strings in O(n) time.

by svat 3y ago

hinkley 3y ago

I’ve seen actual implementations of hash tables claim O(1) amortized insertion time, not O(m). And I misspent a summer about 5 years back thinking I had a constant space overhead mergesort (when what I had was poorly chosen input data. Bummer). I read a lot of mergesort papers then. Nobody mentioned m. I may get bored and check your theory on textbooks, but I suspect you’re letting optimism get the better of you. In a conversation about pragmatism that’s not good. All of my examples at the top were not hypothetical, they were all actual arguments I’ve had with real people or documentation I bitched to someone about. Edit: I mean fuck, even Wikipedia has it wrong: > In sorting n objects, merge sort has an average and worst-case performance of O(n log n). N objects. Not n numbers. If you want to fix the world instead of declaring bankruptcy with me, start there. At least they get space overhead right farther down: > In this case, the notion of "in-place" can be relaxed to mean "taking logarithmic stack space", because standard merge sort requires that amount of space for its own stack usage.

svat 3y ago
Well, Wikipedia is obviously wrong there. I've fixed it to say number of comparison operations: https://en.wikipedia.org/w/index.php?title=Merge_sort&diff=prev&oldid=1185699028 https://en.wikipedia.org/w/index.php?title=Merge_sort&diff=p... Note also that in computational complexity theory, "n" is the length of the input in bits: if you have k strings each of length l, using a regular sort, with a comparison subroutine that takes O(l) time, will take O(kl log k) time — O(k log k) operations each taking O(l) time — which, as n=kl, is O(n log k), upper-bounded by O(n log n). ———— I looked up a couple of influential algorithms textbooks in the meantime, and I must admit this is less clear than I'd have liked (though complexity theorists are very aware of it). • TAOCP vol 3 (which starts with Chapter 5, Sorting) says, on page 5 (in the introduction section of the chapter, where he often says things informally and not exactly): > The time required to sort N records, using a decent general-purpose sorting algorithm, is roughly proportional to NlogN; we make about logN “passes” over the data. This is the minimum possible time, as we shall see in Section 5.3.1, if the records are in random order and if sorting is done by pairwise comparisons of keys. Thus if we double the number of records, it will take a little more than twice as long to sort them, all other things being equal. (Actually, as N approaches infinity, a better indication of the time needed to sort is N(logN)^2, if the keys are distinct, since the size of the keys must grow at least as fast as logN; but for practical purposes, N never really approaches infinity.) It's emphasized less than I'd have liked but he has already mentioned your observation though (and I checked this was present in the first edition in 1973). BTW, note no "O" here: where possible he actually gives the number of machine operations, including the constant factor. TAOCP is very much a "nothing up my sleeve" book, where everything is analyzed down to the constants (where possible) and machine code given. He starts with a very concrete problem where what's being sorted are numbers that each fit in a machine word: > “Memory locations R+1, R+2, R+3, R+4, and R+5 contain five numbers. Write a computer program that rearranges these numbers, if necessary, so that they are in ascending order.” and he makes it clear that what's being sorted are records that contain keys and satellite information, and he's going to mostly assume the keys are integers that fit in a word, sometimes even part of a word. The mention of sorting strings (can get there via the index) is an exercise on page 178: > Design an algorithm to sort strings α1, ..., αn on an m-letter alphabet into lexicographic order. The total running time of your algorithm should be O(m+n+N), where N = |α1| + · · · + |αn| is the total length of all the strings. Note that this running time is better than O(n (N/n) log n) — assuming that the strings are of about equal length N/n, and using a standard sorting algorithm — that I mentioned above. The solution is essentially to construct a trie. • CLRS starts its sorting section with "A sequence of n numbers" and has: > A sorting algorithm describes the method by which we determine the sorted order, regardless of whether we are sorting individual numbers or large records containing many bytes of satellite data. Thus, when focusing on the problem of sorting, we typically assume that the input consists only of numbers. Translating an algorithm for sorting numbers into a program for sorting records… Its index on sorting variable-length items points to p206 (in the 3rd edition) where, similar to TAOCP: > 8-3 Sorting variable-length items > a. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is n. Show how to sort the array in O(n) time. > b. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. Show how to sort the strings in O(n) time.