Constant time, written O(1), describes work whose execution time does not grow with the number of inputs. It is the ideal asymptotic performance classification. section 4.1.2
A nonconstant task can sometimes become constant after an upfront computation. The initial work may be expensive, but repeated constant-time operations can make the trade-off worthwhile. section 4.1.2
Python examples distinguish constant-time operations from operations that still depend on input size:
- Dictionaries and sets support adding, removing, accessing, and checking specific items in constant time. section 4.2.1
- Iterating through a dictionary or set remains O(n), because the work depends on the number of stored items. section 4.2.1
- List membership and insertion at an arbitrary position are mainly O(n), while adding or removing at the end is O(1). section 4.2.2
Checking favorite colors
Read a large color file one line at a time, add each stripped color to a set, then test membership with `"Amber Waves of Grain" in all_colors`. The file-processing loop is linear, but the later membership check is constant time. section 4.2.1
Listing 4.1. Using Python's features to minimize space
all_colors = set()
with open('all-favorite-colors.txt') as favorite_colors_file:
for line in favorite_colors_file: #1
all_colors.add(line.strip()) #2
print('Amber Waves of Grain' in all_colors) #3
Shows a set built from a file and used for constant-time membership checking. section 4.2.1
