There's a simpler and broader point: don't use Big O as the sole means of analysis of a high level language's data structures. The theoretical time/space complexity of a data structure may or may not accurately reflect how it's actually implemented in that language.