Es 2 * N porque puede haber N asociaciones y N actualizaciones. La tabla puede tener entonces hasta 2 * N elementos y para mantener el factor de carga no mayor a 1 se requiere que la cantidad de listas sea 2 * N. De todas formas es aceptable que el tamaño sea N. La longitud promedio de las listas sería 2, que sigue siendo O(1).
En Asociar, es correcta la observación que hacés. Debe ser g->cantidad < (g->tamanio / 2). Quedó corregido el pdf.