Keep reading. At the end there is a linear time agorithm.
Influential Deepu wrote:
> Some person at this group directed me to this page and i found it
> really fitting. Though not linear, but its gives a gr8 algo for the
> same. Go thru it completely !
>
> http://en.wikipedia.org/wiki/Selection
Some person at this group directed me to this page and i found it
really fitting. Though not linear, but its gives a gr8 algo for the
same. Go thru it completely !
http://en.wikipedia.org/wiki/Selection_algorithm
--~--~-~--~~~---~--~~
You received this message be
Deepu, are you sure that this Algo will have an O(n) complexity. None
of my friends and for that matter most of my teachers disagree with it
having a linear time bound.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Donno if it's the right thing to comment here, but some of you might
want to consider what Meggido did for solving some geometric problems -
it's called parametric search... do google for it - it's very very
interesting. His algorithm simulates a parallel algorithm on a serial
system, still achievi
I think you are right. Thanks for your comments..
Regards,
Mukul
--~--~-~--~~~---~--~~
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 unsubscri
Well parallel bubble sort requires more than one processor. When
dealing with algorithms we usually consider just one processor. In
fact as per the link you are using O(n) processors. The number of
comparisons (which is what the complexity is) you are doing overall is
not less than O(n^2). Paralle
Please see here
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/bubbleSort.htm
It says the parallel time complexity of this algorithm is O(n)..
Regards,
Mukul
--~--~-~--~~~---~--~~
You received this message because you are subscribed to th
another soure to find the solution,:)
"introduction to algorithms"
2006/4/25, BiGYaN <[EMAIL PROTECTED]>:
>
> It is rather easy of you want an n(log n) algo.
> But linear I don't thaink so.
>
>
> >
>
--
myblog: http://gnor.net/daizisheng/blog/
--~--~-~--~~~---~--~--
It is rather easy of you want an n(log n) algo.
But linear I don't thaink so.
--~--~-~--~~~---~--~~
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
you are wrong. It is of O(n^2) sine there is a k outer loop and an i
inner loop.
--~--~-~--~~~---~--~~
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.c
Since the iterations of nested for loop are done in parallel, the
complexity is O(n)..
Regards,
Mukul
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to al
Hi Mukul,
I guess the complexity of the proposed algorithm is O(n^2) because you
have two nested loops
(n-2)*(n/2)
It is not linear.please correct me if i missed some concept
Regards,
Aamid
--~--~-~--~~~---~--~~
You received this message because you are sub
Influential Deepu wrote:
> I have been thinking on this problem for quite some time now, but am
> not able to get a linear time algo for the same.
>
> Can nybody help.
See http://en.wikipedia.org/wiki/Selection_algorithm
--~--~-~--~~~---~--~~
You received this m
Parallel bubble sort (shown below) has O(n) complexity.
PARALLEL BUBBLE SORT (A)
For k = 0 to n-2
If k is even then
for i = 0 to (n/2)-1 do in parallel
If A[2i] > A[2i+1] then
Exchange A[2i] ↔ A[2i+1]
Else
for i = 0 to (n/2)-2 do in parallel
If A[2i+1] > A[2i+2
google linear partition algorithm
--~--~-~--~~~---~--~~
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 t
Google for BFPRT (Blum, Floyd, Pratt, Rivest, Tarjan).
This is an algorithm for finding the median in O(n) but it
can be simply modified to find the k-th smallest/largest
element.
Regards,
Daniel
Influential Deepu wrote:
>I have been thinking on this problem for quite some time now, but am
>no
16 matches
Mail list logo
