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)*
>
> >
>
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
