Да скорее всего амортизационное O(1), если hash - функция нормальная. + Интересно, что происходит, когда кол-во элементов < min capacity. Скорее всего будет реалокация и пересчет новой hash - таблицы. Может, из-за того, что зависит от многих параметров и не написали...