Alter auto-increment of table with 16 million rows
It depends, could be an hour or so. Perhaps you may like to give percona toolkit a try; pt-online-schema-change.

pt-online-schema-change alters a table’s structure without blocking reads or writes.
Specify the database and table in the DSN. Do not use this tool before reading its
documentation and checking your backups carefully.


Source: http://www.percona.com/doc/percona-toolkit/2.2/pt-online-schema-change.html