Thanks subramania.. It is very nice explanation.. [?]
On Mon, Jun 6, 2011 at 8:33 PM, subramania jeeva
wrote:
> @Gaurav Aggarwal
> Obviously O(n^2) worst case if we use ordinary quick sort with slight
> modification(Best case O(n))...
> But quick sort can also be done by taking median as element
@Gaurav Aggarwal
Obviously O(n^2) worst case if we use ordinary quick sort with slight
modification(Best case O(n))...
But quick sort can also be done by taking median as element for partition
instead of taking first or last element which will take O(nlgn) worst case
complexity...
But to do the giv
@subramania jeeva
i think the your algorithm will have O(n^2) worst case when the list is
sorted..
On Mon, Jun 6, 2011 at 7:22 PM, subramania jeeva
wrote:
> Tree formation will also take O(nlgn).. For inserting each node It'll take
> O(lgn).. so for inserting n nodes It'll take O(nlgn) time..:)
>
Tree formation will also take O(nlgn).. For inserting each node It'll take
O(lgn).. so for inserting n nodes It'll take O(nlgn) time..:)
Cheers
~ Jeeva ~
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group,
why not form a tree with each node keeping count of elements smaller than
it, i.e nodes in left subtree.
so tree formation is O(n) and tree search is O(logn)
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Mon, Jun 6, 2011 at 12:15 PM, the coder
Use modified quick sort which will stop when the partition function returns
the position k..:)
Cheers
~ Jeeva ~
--
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
Median of median algorithm will do the job...Its worst case performance
analysis is O(n).
The algorithm can be found in wikipedia (search for selection algorithm) but
it is sometimes found difficult to code for it..
I hope following pseudocode will do the job. I am doing it for general Kth
smalles
"This is called finding the k-th order statistic" study the topic from
cormen its there.
On Mon, Jun 6, 2011 at 12:15 PM, the coder wrote:
> hi friendz
>
> given an array how to find the k th largest element in O(N)
> complexity.
>
> --
> You received this message because you are subscribed to
hi friendz
given an array how to find the k th largest element in O(N)
complexity.
--
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
