On Jan 25, 2008 11:47 PM, Sumedh Sakdeo <[EMAIL PROTECTED]> wrote:
> *1) find the second biggest number in a given array of size n. you have to
> use n+logn number of searches or less
>
>
> By this you want to have a complexity less than or equal to n + log n
> rite?
>
> Consider an array { 17 , 4, 3, 18 , 9 , 15, 6 }
> max1 & max2 are index in array.
>
>
> Iteration 1:->i=1 ( as neither arr[max1] < arr[i] nor arr[max2] < arr[i]
> ) so no change
> max1 i
> 17 4 3 18 9 15 6
> max2
>
> Iteration 2:->i=2 ** ( as neither arr[max1] < arr[i] nor arr[max2] <
> arr[i] ) so no change
> **max1 i
> 17 4 3 18 9 15 6
> max2
>
> **
> **Iteration 3:->i=3 ** ( as arr[max1] < arr[i] change max2 to max1 )
> * * i
> 17 4 3 18 9 15 6
> max2 **max1
>
>
> **Iteration 4:->i=4 ** (**as neither arr[max1] < arr[i] nor arr[max2] <
> arr[i] ) so no change)
> * * i
> 17 4 3 18 9 15 6
> max2 **max1
>
> **Iteration 5:->i=5 ** (**as neither arr[max1] < arr[i] nor arr[max2] <
> arr[i] ) so no change)
> * * i
> 17 4 3 18 9 15 6
> max2 **max1
>
> **Iteration 6:->i=6 ** (**as neither arr[max1] < arr[i] nor arr[max2] <
> arr[i] ) so no change)
> * * i
> 17 4 3 18 9 15 6
> max2 **max1
>
> **Second biggest number is arr[max2]
>
> Complexity is O(n)*
The complexity of this algorithm might be O(n), but the question had asked
for n+logn _comparisons_ or less. This algorithm uses 2*n comparisons.
To find the second largest number using only n+logn comparisons, we have to
construct a tournament tree:
1. Construct a tournament with the elements of the array. At each step
the larger of the two elements is advanced to the next level. We will end up
with the largest element on top of the tournament tree.
2. It stands to reason that the second largest element would have
beaten all but the largest element during the tournament. So the second
largest element _has_ to lose to the largest element.
3. We scan the path from the root to the place at the bottom of the
tree where the largest element is. That is, we scan from the root to the
place of the largest element at the bottom of the tree.
4. During this scan, we must come across all the elements which have
lost to the largest element. The second largest element must be one of
these.
The number of comparisons used in the method is n+logn: n comparisons during
the construction of the tournament tree, and because the tree has n
elements, the height of the tree is logn, and thus it takes logn comparisons
to find the second largest element on the path from the root to the leaf.
> **
>
>
> >
>
--
Aravind Narayanan | [EMAIL PROTECTED]
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
