Linear degradation is usually an improvement
given the average programmer's propensity to code up bubble sorts.
Anyhow, performance is typically bounded by the quality of your database and the level of optimization effort you are willing to put into your queries. I mean, if you're going to update 1000 records, that's just gonna take twice as long as updating 500 now, isn't it.
"Whenever you find you are on the side of the majority, it is time to pause and reflect" --Mark Twain
"The significant problems we face cannot be solved at the same level of thinking we were at when we created them." --Albert Einstein
"This is still a dangerous world. It's a world of madmen and uncertainty and potential mental losses." --George W. Bush