The Self-Taught Computer Scientist

Chapter 1 What Is an Algorithm?
15
Best- Case vs. Worst- Case Complexity
An algorithm’s performance can change depending on different factors, such as the type of data you 
are working with. Because of this, when you evaluate an algorithm’s performance, you need to con-
sider its best- , worst- , and average- case complexities. An algorithm’s best- case complexity is how it 
performs with ideal input, and an algorithm’s worst- case complexity is how it performs in the worst 
possible scenario for it. An algorithm’s average- case complexity is how it performs on average.
For example, if you have to search one by one through a list, you may get lucky and find what you 
are looking for after checking the first item in your list. That would be the best- case complexity. 
However, if the item you are looking for isn’t in the list, you would have to search the entire list, which 
is the worst- case complexity.
If you have to search through a list one by one a hundred times, on average you will find what you 
are looking for in O(
n/2) time, which is the same as O(n) time in big- O notation. When comparing 
algorithms, you often start by looking at the average- case complexity. If you want to do a deeper anal-
ysis, you can also compare their best- case and worst- case complexities.
Space Complexity
Computers have finite resources such as memory, so in addition to thinking about an algorithm’s time 
complexity, you should consider its resource usage. Space complexity is the amount of memory space 
your algorithm needs and includes fixed space, data structure space, and temporary space. Fixed space 
Elements
Operations
O(2^n)
O(n^2)
O(n log n)
O(n)
O(log n), O(1)
Figure 1.6: Big O complexity chart

---