Big-O Algorithms Time Complexity

array average access

array worst access

O(1)

O(1)

array average search

array worst search

O(n)

O(n)

array average insertion

array worst insertion

O(n)

O(n)

array average deletion

array worst deletion

O(n)

O(n)

array space complexity worst

O(n)

stack average access

stack worst access

O(n)

O(n)

stack average search

stack worst search

O(n)

O(n)

stack average insertion

stack worst insertion

O(1)

O(1)

stack average deletion

stack worst deletion

O(1)

O(1)

stack worst space complexity

O(n)

linked list average access

linked list worst access

O(n)

O(n)

linked list average insertion

linked list worst insertion

O(1)

O(1)

linked list average deletion

linked list worst deletion

O(1)

O(1)

linked list average search

linked list worst search

O(n)

O(n)

linked list worst space complexity

O(n)

hash table average access

hash table worst access

(not specified)

(not said for this either. look up?)

hash table average search

hash table worst search

O(1)

O(n)

hash table average insertion

hash table worst insertion

O(1)

O(n)

hash table average deletion

hash table worst deletion

O(1)

O(n)

hash table worst space complexity

O(n)

binary search tree average access

binary search tree worst access

O(log(n))

O(n)

binary search tree average search

binary search tree worst search

O(log(n))

O(n)

binary search tree average insertion

binary search tree worst insertion

O(log(n))

O(n)

binary search tree average deletion

binary search tree worst deletion

O(log(n))

O(n)

binary search tree worst space complexity

O(n)

quicksort best time complexity

quicksort average time complexity

quicksort worst time complexity

O(n log(n))

O(n log(n))

O(n^2)

quicksort worst space complexity

O(log(n))

mergesort best time complexity

mergesort average time complexity

mergesort worst time complexity

O(n log(n))

O(n log(n))

O(n log(n))

mergesort worst space complexity

O(n)

insertion sort best time complexity

insertion sort average time complexity

insertion sort worst time complexity

O(n)

O(n^2)

O(n^2)

insertion sort worst space complexity

O(1)

selection sort best time complexity

selection sort average time complexity

selection sort worst time complexity

O(n^2)

O(n^2)

O(n^2)

selection sort worst space complexity

O(1)

linked list (sorted) Find Max

linked list (sorted) Extract Max

linked list (sorted) Increase Key

linked list (sorted) Insert

linked list (sorted) Delete

linked list (sorted) Merge

O(1)

O(1)

O(n)

O(n)

O(1)

O(m+n)

linked list (unsorted) Find Max

linked list (unsorted) Extract Max

linked list (unsorted) Increase Key

linked list (unsorted) Insert

linked list (unsorted) Delete

linked list (unsorted) Merge

O(n)

O(n)

O(1)

O(1)

O(1)

O(1)

min/max heap Find Max

min/max heap Extract Max

min/max heap Increase Key

min/max heap Insert

min/max heap Delete

min/max heap Merge

O(1)

O(log(n))

O(log(n))

O(log(n))

O(log(n))

O(m+n)