The Self-Taught Computer Scientist

Introduction to Algorithms
8
is an algorithm’s order of magnitude. These are the most commonly used classifications for order 
of magnitude in big O notation, sorted from the best (most efficient) to worst (least efficient):
Constant time
Logarithmic time
Linear time
Log- linear time
Quadratic time
Cubic time
Exponential time
Each order of magnitude describes an algorithm’s time complexity. Time complexity is the maximum 
number of steps an algorithm takes to complete as 
n gets larger.
Let’s take a look at each order of magnitude.
Constant Time
The most efficient order of magnitude is called 
constant time complexity. An algorithm runs in constant 
time when it requires the same number of steps regardless of the problem’s size. The big O notation 
for constant complexity is O(1).
Say you run an online bookstore and give a free book to your first customer each day. You store 
your customers in a list called 
customers
. Your algorithm might look like this:
free_books = customers[0]
Your T(
n) equation looks like this:
T(n) = 1
Your algorithm requires one step no matter how many customers you have. If you have 1,000 cus-
tomers, your algorithm takes one step. If you have 10,000 customers, your algorithm takes one step, 
and if you have a trillion customers, your algorithm takes only one step.
When you graph constant time complexity with the number of inputs on the 
x- axis and the number 
of steps on the 
y- axis, the graph is flat (Figure 1.1).
As you can see, the number of steps your algorithm takes to complete does not get larger as the 
problem’s size increases. Therefore, it is the most efficient algorithm you can write because your algo-
rithm’s run time does not change as your data sets grow larger.

---