@Anand, @Abhishek
Thanks for the code and discussion.
However I am not clear as to how the approach suggested is running in
O(n) time. We are dividing and calling bitonicmerge() on two parts
recursively. So this should run in O(n log n) time complexity as
shown below
T(n) = n/2 + 2T(n/2) = n/2 + 2[n/4 + 2T(n/4)] = n/2 + n/2 + 4[n/8 +
2T(n/8)]
= n/2 + n/2 + n/2 + ....log n terms (because we are doubling base
each time so it should be log n terms]
= n [ 1/2 + 1/2 + 1/2 + ...log n terms]
= n [ (log n)/2] = 1/2*(n log n ) = O(n log n)
Also all the following links mention this approach to be O(n log^2(n))
in best case and O(n log n) in worst case
http://www.extreme.indiana.edu/sage/pcxx_ug/subsection3_6_2.html
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm
http://en.wikipedia.org/wiki/Bitonic_sorter
Some explanation on how this is O(n) will be of great help.
Thanks in Advance.
Sourav
On Jul 3, 1:35 am, Abhishek Sharma <jkabhishe...@gmail.com> wrote:
> @Anand: good one
>
> On Sat, Jul 3, 2010 at 2:02 AM, Anand <anandut2...@gmail.com> wrote:
> > This is an example of bitonic sequence if we reverse the bottom half of the
> > array.
> > Sequence is called Bitonics if the sequence of number first
> > increases(ascending order) and then decrease(descending order).
>
> > 1. We need to reverse the bottom half the array to make it bitonic.
> > 2. Appy Bitonic Merge to get the final sorted array.: Complexity.O(n)
>
> > In the below code, I have implemented sorting n/w to sort any kind of array
> > but for bitonic sequence we only bitonic merge function call which take
> > O(n).
> > Refer section Sorting network from Corman for more details
>
> >http://codepad.org/ZhYEBqMw
>
> > On Fri, Jul 2, 2010 at 11:30 AM, ANKUR BHARDWAJ <ankibha...@gmail.com>wrote:
>
> >> Given an array of n elements and an integer k where k<n. Elemnts
> >> {a[0].....a[k] and a[k+1].....a[n] are already sorted. Give an
> >> algorithm to sort in O(n) time and O(1) space.
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algoge...@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> >> .
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
