'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