I think O(n) means a gradual degradation (linear) so a statement that >100 items in one or other DB "causing" problems is a bit misleading - it depends on your horsepower and traffic.
A quick look at one of my pfSense VMs shows 136 odd items in the SAD. Can't say things are unusable by any stretch of the imagination.
However a better algo is always a good idea in any area of IT - the bloody things are cut n paste out of many textbooks! Amazing something as old as IPSEC has only just received this treatment.
Cheers
Jon