No it would remain roughly O(1), the look up does not grow with the number of votes to place, it's constant size per user. The implementation would be like a FIFO queue of size N, @rycharde suggests N = 10.

steemd uses a local DB to cache information, as far as I have seen from very cursory glances. The real cost would be a fixed size increase to the cache per user. As we scale this could have a big impact of witness server resources and might be an argument against it. But then again this is the job of a witness and if it's a needed feature they (we I guess!) will have to step up.