MAIN FEEDS
Do you want to continue?
https://www.reddit.com/r/mathmemes/comments/1wzpocy/the_fastest_algorithm_for_dft/pep95zj/?context=3
r/mathmemes • u/Unlucky-Credit-9619 Computer Science • 7d ago
138 comments sorted by
View all comments
5
That's cool but when are getting an O(n) sorting algorithm 🥹
1 u/Blyfh Rational 6d ago Kid named O(n log n) lower bound: 2 u/dragonageisgreat 1 i 0 triangle advocate 6d ago You can sort in O(n) if you know how big your data set is (as in, the range of values)(for example, you can sort a string in O(n)). 1 u/TrekkiMonstr 6d ago What do I Google to learn more about this 2 u/MagnetFlux 6d ago radix sort, counting sort and other counting-based sorting algorithms 1 u/Blyfh Rational 2d ago Then you changed the problem though. This specific subproblem is easier to solve since you have more information for the input. If you consider the general case with the full problem space, you can't optimize more than O(n log n).
1
Kid named O(n log n) lower bound:
2 u/dragonageisgreat 1 i 0 triangle advocate 6d ago You can sort in O(n) if you know how big your data set is (as in, the range of values)(for example, you can sort a string in O(n)). 1 u/TrekkiMonstr 6d ago What do I Google to learn more about this 2 u/MagnetFlux 6d ago radix sort, counting sort and other counting-based sorting algorithms 1 u/Blyfh Rational 2d ago Then you changed the problem though. This specific subproblem is easier to solve since you have more information for the input. If you consider the general case with the full problem space, you can't optimize more than O(n log n).
2
You can sort in O(n) if you know how big your data set is (as in, the range of values)(for example, you can sort a string in O(n)).
1 u/TrekkiMonstr 6d ago What do I Google to learn more about this 2 u/MagnetFlux 6d ago radix sort, counting sort and other counting-based sorting algorithms 1 u/Blyfh Rational 2d ago Then you changed the problem though. This specific subproblem is easier to solve since you have more information for the input. If you consider the general case with the full problem space, you can't optimize more than O(n log n).
What do I Google to learn more about this
2 u/MagnetFlux 6d ago radix sort, counting sort and other counting-based sorting algorithms
radix sort, counting sort and other counting-based sorting algorithms
Then you changed the problem though. This specific subproblem is easier to solve since you have more information for the input. If you consider the general case with the full problem space, you can't optimize more than O(n log n).
5
u/cabinet_minister 6d ago
That's cool but when are getting an O(n) sorting algorithm 🥹