The statement says that this can be achieved using exactly n+ceiling(lg(n))-2 comparisons in the worst case. I thought for a long time but didn't get the right idea.
This post by n1b-algo gives a detailed explanation.
Its main idea is to build a comparison tree and check the elements "knocked out" by the smallest one afterwards. The smallest element is placed at the root, and it beats exactly one element at each level except the root, so there are ceiling(lg(n))-1 elements to check in total, since the binary tree with n leaves at the bottom level and without any other leaves has ceiling(lg(n)) levels excluding the root.
No comments:
Post a Comment