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.
O(g(x)) | Name |
---|---|
1 | constant (perfect scalability) |
log n | logarithmic |
n | linear |
n2 | quadratic |
n3 | cubic |
2n | exponential (evil) |
n! | factorial (pure evil) |