CS 1332 Final Exam Big-O Review

Assume worst case unless specified

Adding to the back of an ArrayList

O(1)*

Adding to any index ArrayList

O(n)

Removing from an ArrayList

O(n)

Removing from back of an ArrayList

O(1)

Accessing from an ArrayList

O(1)

Accessing from a SLL no tail

O(n)

Adding to the front of a SLL

O(1)

Adding to the front of a DLL

O(1)

Adding to the back of a SLL w/ tail

O(1)

Adding to the back of a DLL

O(1)

Removing from the back of a SLL

O(n)

Removing from the back of a DLL

O(1)

Removing from the front of a SLL

O(1)

Removing from the front of a DLL

O(1)

Pushing onto a SLL-backed stack

O(1)

Popping off a SLL-backed stack

O(1)

Pushing onto an Array-backed stack

O(1)*

Popping off an Array-backed stack

O(1)

Enqueuing into a SLL-backed queue

O(1)

Dequeuing from a SLL-backed queue

O(1)

Enqueuing into an Array-backed queue

O(1)*

Dequeuing from an Array-backed queue

O(1)

addFirst() in a DLL-backed Deque

O(1)

addLast() in a DLl-backed Deque

O(1)

removeFirst() in a DLL-backed Deque

O(1)

removeLast() in a DLL-backed Deque

O(1)

addLast() in an Array-backed Deque

O(1*

addFirst() in an Array-backed Deque

O(1)*

removeFirst() in an Array-backed Deque

O(1)

removeLast() in an Array-backed Deque

O(1)

Performing any traversal on a tree

O(n)

Worst case of adding to a BST

O(n)

Average case of adding to a BST

O(log n)

Worst case of removing from a BST

O(n)

Average case of removing from a BST

O(log n)

Best case of searching BST

O(1) - when data is in root

Average case of searching BST

O(log n)

Worst case of searching BST

O(n)

Adding to a heap

O(log n)*

Removing from a heap

O(log n)

BuildHeap()

O(n)

Building a heap by calling add() on each element

O(n log n)

Adding to a hashmap Ex.Chaining

O(n)

Removing from a hashmap

O(n)

Searching in a hashmap

O(n)

Adding to an AVL

O(log n)

Removing from an AVL

O(log n)

Searching in an AVL

O(log n)

Getting the height of AVL

O(1)

Traversing an AVL

O(n)

Best case of searching, adding, or removing from a SkipList

O(1)

Average case of searching, adding, or removing from a SkipList

O(log n)

Worst case of searching, adding, or removing from a SkipList

O(n) - degenerates to just a LinkedList

Worst case of space complexity for a SkipList

O(n log n)

Removing from 2-4 tree

O(log n)

Adding to a 2-4 tree

O(log n)

Searching in a 2-4 tree

O(log n)

Worst case of Bubble Sort

O(n^2) - reverse sorted array

Best case of Bubble Sort

O(n)

Worst case of Insertion Sort

O(n^2) - reverse sorted array

Best case of Insertion Sort

O(n)

Selection Sort

O(n^2)

Worst case of Cocktail Shaker Sort

O(n^2) - reverse sorted array

Best case of Cocktail Shaker Sort

O(n)

Merge Sort

O(n log n)

Worst case of In-Place Quicksort

O(n^2) - pivot is always min or max value of subarray

Best case of In-Place Quicksort

O(n log n)

LSD Radix Sort

O(kn)

Worst case of QuickSelect

O(n^2)

Best case of QuickSelect

O(n)

Best case of Brute Force if no occurrences of pattern are in text

O(n)

Worst case of Brute Force if no occurrences of pattern are in text

O(nm)

Best case of Brute Force to find single occurrence

O(m)

Worst case of Brute Force to find single occurrence

O(mn)

Best case of Brute Force to find all occurrences

O(n)

Worst case of Brute Force to find all occurrences

O(mn)

Creating the Last Occurrence Table

O(m)

Best case of Boyer Moore if no occurrences of pattern are in text

O(m + n/m)

Worst case of Boyer Moore if no occurrences of pattern are in text

O(mn)

Best case of Boyer Moore to find single occurrence

O(m)

Worst case of Boyer Moore to find single occurrence

O(mn)

Best case of Boyer Moore to find all occurrences

O(m + n/m)

Worst case of Boyer Moore to find all occurrences

O(mn)

Using KMP to find all occurrences

O(m + n)

Using KMP if no occurrences of the pattern are in the text

O(m + n)

Best case of KMP to find single occurrence

O(m)

Worst case of KMP to find single occurrence

O(m+n)

Creating the Failure Table

O(m)

Best case of Rabin Karp if no occurrences of pattern are in text

O(m + n)

Worst case of Rabin Karp if no occurrences of pattern are in text

O(mn)

Best case of Rabin Karp to find single occurrence

O(m)

Worst case of Rabin Karp to find single occurrence

O(mn+m)

Worst case of Rabin Karp to find all occurrences

O(mn+m)

Best case of Rabin Karp to find all occurrences

O(m + n)

Space complexity of Adjacency Matrix

O(|V|^2)

Space complexity of Adjacency List

O(|V|²)

Space complexity of Edge List

O(|E|)

Big O of Depth First Search

O(|V| + |E|)

Big O of Breadth First Search

O(|V| + |E|)

Big O of Dijkstra's

O(|E| log |E|)