CSE 332 Runtimes

Stacks-ArrayList Push

Best: O(1) Worst: O(n)

Stacks-ArrayList Pop

Best/Worst: O(1)

Stacks-ArrayList Peek/Top

Best/Worst: O(1)

Stacks-ArrayList Search

Best/Worst: O(n)

Stacks-LinkedList Push

Best/Worst: O(1)

Stacks-LinkedList Pop

Best/Worst: O(1)

Stacks-LinkedList Peek/Top

Best/Worst: O(1)

Stacks-LinkedList Search

Best/Worst: O(n)

Queue-Circular Array Enqueue

Best: O(1) Worst: O(n) (resized)

Queue- Circular Array Dequeue

Best/Worst: O(1)

Queue-Circular Array Front/Peek

Best/Worst: O(1)

Queue-Circular Array Search

Best/Worst: O(n)

Queue-LinkedList Enqueue

Best/Worst: O(1)

Queue-LinkedList Dequeue

Best/Worst: O(1)

Queue-LinkedList Front/Peek

Best/Worst: O(1)

Queue-LinkedList Search

Best/Worst: O(n)

BST Search

Best: O(log n). Worst: O(n)

BST Insert

Best: O(log n). Worst: O(n)

BST Delete

Best: O(log n). Worst: O(n)

Heap Insert

Best: O(1). Worst: O(log n)

Heap Delete min/max

Best: O(log n). Worst: O(log n)

Heap Peek min/max

Best/Worst: O(1)

Heap Search

Best: O(1). Worst: O(n)

Percolate Up/Down

Best: O(1). Worst: O(log n)

Floyd's BuildHeap Insert N items

O(N)

AVL Search, Insert, Delete

Best/Worst: O(log n)

AVL Traversal

Best/Worst: O(n)

decreaseKey/increaseKey

O(log n)