Linear time means that an algorithm’s running time grows in proportion to its input size. Written as O(n), it describes growth that looks like a straight line when input size and running time are graphed. section 4.7 section 4.16
Use O(n) to reason about algorithms whose work scales with the number of input elements:
- Scanning every element once requires linear time, even when the average search examines only about half the elements. section 4.14
- Constant factors such as loop increments and comparisons do not change the linear classification, but calls inside the loop may add hidden costs. section 4.14
- Running time and extra memory are separate measurements: an algorithm can take O(n) time while using O(1) extra space. section 4.14 section 4.12
Linear search
A linear search checks array elements in order until it finds the target or reaches the end. An unsuccessful search checks all n elements, so its running time is O(n). section 4.14
def linear_search(self, target):
for i in range(self._size): # repeat F(n) times
if self._array[i] == target: # cost: O(1)
return i # cost: O(1)
elif self._array[i] > target: # cost: O(1)
return None # cost: O(1)
return None # cost: O(1)
The implementation makes the growth visible: the loop may repeat once for each element, while each comparison and return takes constant time. section 4.14
