Putting It All Together

Consider the original example of having to count the number of people in a room. Pretend you can count one person per second. Then, if there are seven people in the room, it will take seven seconds to count them. More generally, given n people it will take n seconds to count everyone. Thus, you can say this algorithm is O(n). What if the task was to dance in front of everyone in the room? Because it would take the same amount of time to dance whether there were five or five thousand people in the room, this task is O(1). See Table C.1 for other common complexities.

Table C.1. Table of Common Time Complexity Values

O(g(x))	Name
1	constant (perfect scalability)
log n	logarithmic
n	linear
n2	quadratic
n3	cubic
2n	exponential (evil)
n!	factorial (pure evil)

What is the complexity of introducing everyone in the room to everyone else? What is a possible function that models this algorithm? If it took thirty seconds to introduce each person, how long would it take to introduce 10 people to each other? What about one hundred people to each other?