Answer Happy

Imagine you plan to invite a bunch of people to a dinner party. Let n be the number of people invited to the party. If you invite 10 people, you will have to shake hands ten times. If you double the number of guests, it will take you twice as long. This is a linear increase, and the time it will take you to shake everyone's hand can be expressed as O(n). Now, let's suppose everyone wants to shake hands, but for some strange reason only one pair can shake hands at a time. As n increases, how much longer will this meet and greet take? Give a big-O estimate for the meet-and-greet time and justify your answer. (Hint: How many pairs are there?)