Aravind Narayanan's solution involving the tournament tree does solve
the problem in n + log_2 n comparisons. It takes n-1 comparisons to
find the largest number in the array. As he explains, once you know
the largest number, you only have to check the numbers it was compared
with in the tournament tree, and there can be no more than
ceiling(log_2 n) numbers that were compared to the largest number. It
takes ceiling(log_2 n)-1 comparisons to find the largest of those.
Therefore, the total number of comparisons is n+ceiling(log_2 n)-2.
For n = 10, this is 10 + 4 - 2 = 12, as you require.
Dave
On Feb 3, 7:34 am, "kamalakannan .h" <[EMAIL PROTECTED]> wrote:
> hellow,
> thanks for taking pains to replying. this is not what i meant.
> i asked for n+logn comparisons. like see how much comparisons you have done
> it will be over 2n. if ther are 10 numbers then you should do less than 12
> comparisons
>
> On 1/25/08, 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)*- Hide quoted text -
>
> - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
