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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---