Studied by 65 people
Looks like no one added any tags here yet for you.
O(1)
Constant (fastest speed)
O(log N)
Logarithmic (2nd fastest speed)
O(N)
Linear (3rd fastest speed)
O(N log N)
Linearithmic (3rd slowest speed)
O(N^2)
Quadratic (2nd slowest speed)
O(2^N)
Exponential (slowest speed)
Traversing the Array
O(N)
Search for an item unknown in an Array
O(N) or O(log N)
Remove any item location unknown in an Array
O(N)
Get any item location unknown in an Array
O(1)
Add item at the end of an Array
O(1)
Add item at the front of an Array
O(N)
Traversing an array in a Linked List
O(N)
Search for an item in a Linked List
O(N)
Remove any item location unknown in a Linked List
O(N)
Add item at the end of a Linked List
O(N)
Add item at the front of a Linked List
O(1)
Add item at the end of a Double Linked List (almost every property is identical to Linked List except this)
O(1)
Traversing an array in a Binary (Search) Tree
O(N)
Search for an item in a Binary (Search) Tree
O(log N)
Remove any item location unknown in a Binary (Search) Tree
O(log N)
Get any item location unknown in a Binary (Search) Tree
O(log N)
Add item at the end of a Binary (Search) Tree
O(log N)
Add item at the front of a Binary (Search) Tree
O(1)
Traversing an array in an ArrayList
O(N)
Search for an item in an ArrayList
O(log N) or O(N)
Remove any item location unknown in an ArrayList
O(N)
Get any item location unknown in an ArrayList
O(1)
Add item at the end of an ArrayList
O(1)
Add item at the front of an ArrayList
O(N)
"add" / "remove" / "contains" in a Tree Set
O(log N)
"put" / "get / "containsKey" in a Tree Map
O(log N)
"add" / "remove" / "contains" in a Hash Set
O(1)
"put" / "get / "containsKey" in a Hash Map
O(1)
Best/Average/Worst Case for Linear Search
O(1) / O(N) / O(N)
Best/Average/Worst Case for Binary Search
O(1) / O(log N) / O(log N)
Best/Average/Worst Case for Selection Sort
O(N^2)
Best/Average/Worst Case for Bubble Sort
O(N^2)
Best/Average/Worst Case for Insertion Sort
O(N) / O(N^2) / O(N^2)
Best/Average/Worst Case for Merge Sort
O(N log N)
Best/Average/Worst Case for Quick Sort
O(N log N) / O(N log N) / O(N^2)
Best/Average/Worst Case for Heap Sort
O(N log N)
Note
Flashcard