What's the complexity of renaming a column in MySql?

It can be an O(1) operation if only the name is changing, see:

https://dev.mysql.com/doc/refman/8.0/en/alter-table.html

and search for:

Renaming, Redefining, and Reordering Columns

That is in a section that explains that the operation only modifies table metadata.

Back in MySQL 5.5 the manual says it works there too, except for InnoDB tables.

Unfortunately, it is O(N). Internally MySQL creates a new table with the desired structure, copies all your data over to that, and then finally swaps datafiles to effect a drop of the original table with a "rename" of the new. You can find this in MySQL's manual -- it's buried (hence why I can't find the direct link for you right this moment), but it's there.

A possibility for you to consider that I've used when restructuring large tables is essentially to take these same steps yourself:

1. Create new_table with the desired structure
2. Run INSERT INTO new_table (SELECT * FROM old_table) -- note that you'll need to in fact be explicit with columns at least for the INSERT, and I recommend for the SELECT as well (that way you'll have a pattern you can follow when re-ordering columns as well).
3. Drop the original and rename the new

The advantage to doing it yourself is that you can do the schema change and the initial population while your database is live, and then lock the original before you do a final update for any data that may have changed in the meantime and then the final swap-it-into-place. (Note that this assumes you have some mechanism -- maybe a TIMESTAMP field -- to identify rows that change in the meantime.)