complexity (PDF)

Vector Operation
PopBack(), Clear()
Front(), Back()
Empty(), Size(), Capacity()
bracket operator []
PushBack(t)
SetSize(n), SetCapacity(n)
assignment operator =
Constructors, Destructor
Display(os,ofc)
Dump(os)

Runtime Complexity
Actual
Θ(1)

Requirement
O(1)

Amortized Θ(1)
O(n)
Θ(n), n = Capacity()
Θ(n), n = Capacity()

Amortized O(1)
O(n)
O(n), n = Capacity()
O(n), n = Capacity()

Θ(n), n = Size()
Θ(n), n = Capacity()

* Note that Θ(1) and O(1) are equivalent
List Operation
PushFront(), PushBack()
Insert(), PopFront()
PopBack(), Remove()
Front(), Back()
Empty()
Default Constructor
Size(), Clear(), Remove()
assignment operator =
Copy Constructor,
Assignment operator,
Destructor
Display(os,ofc)
Dump(os)
* Note that Θ(1) and O(1) are equivalent

Runtime Complexity
Actual
O(1)

Requirement
O(1)

Θ(n), n = Size()
Θ(n), n = Size()
Θ(n), n = Size()

O(n), n = Size()
O(n), n = Size()
O(n), n = Size()

Θ(n), n = Size()
Θ(n), n = Size()

Deque Operation
PopFront(), PopBack(), Clear()
Front(), Back()
Empty(), Size()
bracket operator []
PushFront(t), PushBack(t)
assignment operator =
Constructors, Destructor
Display(os,ofc)
Dump(os)
* Note that Θ(1) and O(1) are equivalent

Runtime Complexity
Actual
Θ(1)

Requirement
O(1)

Amortized Θ(1)
Θ(n), n = Size()
Θ(n), n = Size()

Amortized O(1)
O(n), n = Size()
O(n), n = Size()

Θ(n), n = Size()
Θ(n), n = Size()