First find out the largest element and it requires n-1 comparison.
Lets say we have 8 elements then we need 7 comparison to decide
largest. Imagine the tree structure that you will use to find out
largest.
21
15 21
9 15 8 21
2 9 11 15 7 8 9 21
Notice that second largest will be be smaller than largest and larger
than any other item in the list. So it is sure that second largest
will loose in comparison with largest. Hence Second largest will be
searched only with the items that got compared with largest item.
Number of items that got compared with largest is logn(height of
tree).
logn-1 comparison is needed to find largest among them.
Total comparison to find second largest = (n-1) + (logn-1)
On Oct 10, 11:52 pm, sankalp <sankalpmishr...@gmail.com> wrote:
> can anyone give me algorithm for finding the second largest element in
> array using tournament method requiring n+logn-2 compariso
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
