'Why does Cracking the Coding Interview, 6th Edition say "X insertions take O(2X) time"?
On page 43, the last line is "Therefore, X insertions take O(2X) time. The amortized time for each insertion is O(1). "
But on page 41, the author said "Drop the Constants". So, X insertions take O(X) time, not O(2X), right?
Solution 1:[1]
O(2X) = O(X) = O(100X). It's normal to drop the constants but it's not required. O(X) is the same thing as O(2X) so it's not wrong to say O(2X).
It's akin to writing 9/3. It's not wrong, although of course people usually reduce it to 3.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | John Kugelman |
