There may be a language problem here, but I think where the OP says
_searches_, he really means _comparisons_. Since O(log n) < O(n), it
doesn't make any sense to say that the complexity is O(n + log n),
because that is just O(n). Thus, I think the requirement is to use no
more than n + log n comparisons, and probably log represents log_2.
Your algorithm can use as many as 2n comparisons (consider when the
array already is sorted), so I don't think it satisfies the
requirement.
Dave
On Jan 25, 12:17 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)*
>
> secondbiggestnumber.cpp
> 1KDownload
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
