b) Since this decision tree uses <, =, and >, and must compare each pair of adjacent elements in the array, the lower bound is O(nlogn).
c) Yes, it is a tight lower bound. Since all adjacent elements need to be compared, there is no way for it to happen any faster.
2. A).
A)	It is well known that problem Q has a tight lower bound of Omega(n logn).
-	Transform each element x of Q into a point (x,0) (Cost1 ∈ Omega(n logn)
B)	Find MST for these points.
-	Cost2 = Cost(P)
C)	Traverse MST to look for a zero-length edge
-	Cost3 ∈ Theta(n) because MST has n-1 edges.
Cost(Q) = Cost1 + Cost2 + Cost3
= Costreduction + Cost(P) where Costreduction ∈ Theta(n)
B). Reasoning by contradiction: If P could be solved at a cost that is cheaper than Omega(n logn), Cost(P) ∈ o(n logn), therefore cost(Q) ∈ o(n logn). Therefore Cost(P) ∈ Omega(n logn)
C. Yes, Omega(n logn) is a tight lower bound for P, since it is reducible from Q.

4. a) It will have to read a “1” n times.
b) The number of “0”s can change depending on the number of “1”s.