I wonder if it'll be worth it to cache the count for each constituent collection. Also cache both endIndex values and the starting index of the longer collection's suffix, if the collections are unequal in length. The only time that inappropriately O(n) stuff happens would be in the initializer, to set up this cache.
Edit: the last "to" was accidentally "so."