Using a decision tree and your answer to part (a), show that any algorithm that correctly merges two sorted lists must perform at least 2n − o(n) comparisons.
answer from part (a): 2n over n ways to divide 2n numbers into two sorted lists, each with n numbers (2n over n) <= 2^h
h >= lg(2n)! / (n!)^2
= lg(2n!) - 2lg(n!)
= Θ(2nlg(2n)) - 2Θ(nlg(n)) <----
= Θ(2n) <----
I don't understand the last step. How can it be Θ(2n)?
You can represent logarithm of product as sum of separate logarithms (the first property here):
2*n*lg(2*n) = 2*n*(lg(2) + lg(n)) = 2*n*(1 + lg(n))
So
2*n*(1 + lg(n)) - 2*n*lg(n) =
2*n+ 2*n*lg(n)) - 2*n*lg(n) = 2*n