If we merge two sorted arrays, let A, and B, of size n both, into
another array of size 2n, lets call it M. then the lower bound for any
algorithm is (2n-1). It's obvious, that to guarantee correctness of algo
we need to do atleast(atmost too) 2n-1 number of comparison.
My doubt is, while proving it using comparison tree, (where we compare
two elements and only possible two branches are yes or no), what will be
the number of leaves in the comparison three.
will it be 2nCn (i.e. (2n)!/(n! n!) ) or
2^(2n)+1
tree will look like
A[1] < B[1]
yes no
A[2]<B[1] A[1]<B[2]
yes No yes
No
it will grow like this, until 2n-1 comparisons are done(in the worst
case/longest root to leaf path in the tree).
Regards,
Deepak
--
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?hl=en.
