Какова временная сложность удаления элемента из начала вектора?

Временная сложность удаления элемента из начала std::vector составляет O(n), где n - количество элементов в векторе. Это связано с тем, что после удаления первого элемента все последующие элементы должны быть сдвинуты в памяти на одну позицию влево.