9 7 our analysis addresses both the average case and the worst case for determining the best allocation method