> Where, where does it say that std::deque is supposed to have O(sqrt(n)) space requirement as worst case?

Nowhere! Where did I even claim it said that anywhere?!