This is not generally the case. Practically speaking, big O notation is almost always bounded. The clojure vector implementation has a maximum count of 2^32, therefore the behaviour at infinity is O(SomeException)