tag:blogger.com,1999:blog-759530137113893554.post4741038432292026615..comments2023-08-06T01:49:39.814-07:00Comments on Puzzles, Maths and Algorithms: Finding Second Smallest ElementUnknownnoreply@blogger.comBlogger6125tag:blogger.com,1999:blog-759530137113893554.post-55153717137734167572012-07-19T09:59:52.550-07:002012-07-19T09:59:52.550-07:00Hi Anon. A naive approach would be fine if cost of...Hi Anon. A naive approach would be fine if cost of comparison is small. <br /><br />Imagine that the N items are database transactions and a comparison cost is large (say date comparison + string matching + expression evaluations). Then tournament approach makes more sense. <br /><br />Again I am making cases but the solution is interesting mostly from academic point-of-view.Adityanoreply@blogger.comtag:blogger.com,1999:blog-759530137113893554.post-37018376306087231002012-07-18T16:47:43.456-07:002012-07-18T16:47:43.456-07:00The tournament approach sounds like a great idea b...The tournament approach sounds like a great idea because the number of comparisons made is very small, but the other half of the story is that you are doing about N memory writes as opposed to no memory writes (if you kept just the top 2 values, those would likely end up being in registers), and you are using extra space. In practice, I would be surprised if this approach could outperform a naive implementation that just maintains the top 2 values at all times.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-759530137113893554.post-62549244762098757742012-05-07T23:17:44.501-07:002012-05-07T23:17:44.501-07:00Ignore my comment. I was wrong.Ignore my comment. I was wrong.shrivatsannoreply@blogger.comtag:blogger.com,1999:blog-759530137113893554.post-81705077741055113712012-05-07T22:52:44.005-07:002012-05-07T22:52:44.005-07:00I am sorry, I am not sure if I understand this. Wh...I am sorry, I am not sure if I understand this. What happens when the input array is sorted? <br /><br />{1, 2, 3, 4}<br /><br />Won't the algorithm fail?shrivatsannoreply@blogger.comtag:blogger.com,1999:blog-759530137113893554.post-7354177326140689042011-03-09T00:56:51.682-08:002011-03-09T00:56:51.682-08:00I encountered this problem as an exercise in CLRS ...I encountered this problem as an exercise in CLRS and failed to figure out where the lg(n) come from. The phrase "knocked out by 1" explains everything.<br />Thank you.youbohttps://www.blogger.com/profile/16926620632272616369noreply@blogger.comtag:blogger.com,1999:blog-759530137113893554.post-24533562037167169612010-05-01T13:16:22.530-07:002010-05-01T13:16:22.530-07:00Great article! And it becomes so easy to code it w...Great article! And it becomes so easy to code it with Python. In fact, a certain company gave reference to your blog and asked to solve the problem.Barun Sahahttps://www.blogger.com/profile/16299150319108966704noreply@blogger.com