Polyomino question

[David Wilson]

A couple of variantions on this theme:

Let a(n) be the size of the smallest polyomino cover for the n-ominoes.

Any n-omino fits into an n x n square so a(n) <= n^2.  By abutting each omino to 
the bottom and left side of the square, the omino will fit into "right 
isosoceles" polyomino so a(n) <= (n^2+n)/2.  If we also rotate the omino so its 
height does not exceed its width, we can cap it at height ceil(n/2) <= (n+1)/2, 
so that a(n) <= (3n^2 + 4n + 1)/8.  This gives us a(n) is O(n^2) with c <= 3/8. 
I imagine we can do better.  Can we get a(n) to be O(n log n)?