“Yesterday the Census Bureau announced the new apportionment of the 435 representatives to states based on the 2010 census. Illinois lost one representative. Texas gains four. Not only do these affect the makeup of the House of Representatives but also the Electoral College that chooses the president.

Since 1940 the apportionment is not done by a specific formula but by an algorithm. </em>

• Input: Pop, a population array for the 50 states.
• Output: Rep, a representatives array for the 50 states.
• Let Rep[i] = 1 for each state i.
• For j = 51 to 435
  • Let i = arg max Pop[i]/sqrt(Rep[i]*(Rep[i]+1))
  • Rep[i] = Rep[i]+1

This algorithm called the Huntington-Hill method or the Method of Equal Proportions, minimizes the relative difference between sizes of congressional districts. Check out the Census Bureau video The Amazing Apportionment Machine.”

“Implemented naively the running time is O(rn) for n the number of states and r the number of representatives. I’ll leave it to you readers to find better implementations. Can I compute how many representatives New Jersey gets from Pop in o(n) space?

Of course with n=50 and r=435 the numbers don’t get big enough to cause any problem at all for today’s computers. I wonder how long it took in 1940?</em> “ via Computational Complexity: America’s Most Important Algorithm (computationalcomplexity.org)