В среднем O(1) амортизированно: при достаточной cap - просто запись и увеличение len. При нехватке cap - выделение нового массива и копирование - O(n), но происходит редко, поэтому амортизированная стоимость добавления одного элемента - константа.