tag:blogger.com,1999:blog-9149523927864751087.post6550452315916667947..comments2024-03-26T09:43:01.052-07:00Comments on Small Datum: It is all about the constant factorsMark Callaghanhttp://www.blogger.com/profile/09590445221922043181noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-9149523927864751087.post-31176688034468807202020-01-07T10:23:38.746-08:002020-01-07T10:23:38.746-08:00Thank you anonThank you anonMark Callaghanhttps://www.blogger.com/profile/09590445221922043181noreply@blogger.comtag:blogger.com,1999:blog-9149523927864751087.post-5663731123218874012020-01-07T10:21:27.583-08:002020-01-07T10:21:27.583-08:00This reminded me of MySQL bug 49047, reported by H...This reminded me of MySQL bug 49047, reported by Harrison - deadlock detection could be O(n^2), which then got improved.<br /><br />Big-O is useful, but I agree, maybe overly relied-on. One algorithm might perform much better on real datasets, but have a worse big-O because of particular, unusual worst-case scenarios. There are so many factors besides worst-case analyses.<br /><br />I like to point out my O(1) - for a fixed disk size - lookup algorithm, better than any index, apparently - scan the entire disk for your entry. <br /><br />Whether you scan RAM or SSD or HDD is "just a constant factor" for performance, so who needs caches, buffers, pre-fetching, etc?Ben Krughttps://www.linkedin.com/in/ben-krug-168a7110a/noreply@blogger.comtag:blogger.com,1999:blog-9149523927864751087.post-80072057109594517822020-01-07T08:24:39.981-08:002020-01-07T08:24:39.981-08:00https://bugs.mysql.com/bug.php?id=84958
(InnoDB...https://bugs.mysql.com/bug.php?id=84958<br />(InnoDB's MVCC has O(N^2) behaviors)<br /><br />https://bugs.mysql.com/bug.php?id=67044<br />(Secondary index updates make consistent reads do O(N^2) undo page lookup)Anonymousnoreply@blogger.com