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.
Ah right, I forgot the post suggested tracking the last 10 votes. I was thinking of all votes within a time period. The problem then becomes - what if the person self-votes 100%, then places
-9-10 other votes at 1%? Maybe you only add the vote to the queue if the vote percentage is above a certain threshold?I think simply multiplying by the weight would be the most effective instead of using a threshold.
Perhaps you have an opinion @rycharde?