title: Finding lower bound on time complexity of finding k pairs
body: <p>We are given n bolts and n nuts of different sizes, where each bolt exactly matches one nut. Our goal is to find the matching nut for each bolt. The nuts and bolts are too similar to compare directly; however, we can test whether any nut is too big, too small, or the same size as any bolt.</p>
  
  <p>Prove that in the worst case Ω(n + k log n) nut-bolt comparisons are required to find k matching pairs.</p>
  
  <p>I'm thoroughly stumped on how to do this, I figure a 3-ary decision tree with for this would need n^k nodes, thus giving klog(n) for the height of the tree, but I can't figure out where the +n comes from.</p>