CS 1332 Final Exam Plus Time Complexities
Studied by 0 people
Learn
Practice Test
Spaced Repetition
Match
Flashcards1/141
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced |
|---|
No study sessions yet.
142 Terms
O(n)
add to first index of ArrayList
O(1)*
add to last index of ArrayList
O(n)
add to any index of ArrayList
O(n)
remove from first index of ArrayList
O(1)
remove from last index of ArrayList
O(n)
remove from any index of ArrayList
O(1)
search at index in ArrayList
O(n)
search for specific value in ArrayList
O(n)
resize ArrayList
O(1)
add to first index of SLL, no tail
O(n)
add to last index of SLL, no tail
O(n)
add to any index of SLL, no tail
O(1)
remove from first index of SLL, no tail
O(n)
remove from last index of SLL, no tail
O(n)
remove from any index of SLL, no tail
O(n)
search at index in SLL, no tail
O(n)
search for specific value in SLL, no tail
O(1)
add to first index of SLL, with tail
O(1)
add to last index of SLL, with tail
O(n)
add to any index of SLL, with tail
O(1)
remove from first index of SLL, with tail
O(n)
remove from last index of SLL, with tail
O(n)
remove from any index of SLL, with tail
O(n)
search at index in SLL, with tail
O(n)
search for specific value in SLL, with tail
O(1)
add to first index of CSLL
O(1)
add to last index of CSLL
O(n)
add to any index of CSLL
O(1)
remove from first index of CSLL
O(n)
remove from last index of CSLL
O(n)
remove from any index of CSLL
O(n)
search at index in CSLL
O(n)
search for specific value in CSLL
O(1)
add to first index of DLL with tail
O(1)
add to last index of DLL with tail
O(n)
add to any index of DLL with tail
O(1)
remove from first index of DLL with tail
O(1)
remove from last index of DLL with tail
O(n)
remove from any index of DLL with tail
O(n)
search at index in DLL with tail
O(n)
search for specific value in DLL with tail
O(1)*
add to last index of Stack (array-backed)
O(1)
remove from last index of Stack (array-backed)
O(n)
resize Stack (array-backed)
O(1)*
add to last index of Queue (array-backed)
O(1)
remove from first index of Queue (array-backed)
O(n)
resize Queue (array-backed)
O(1)*
add to first index of Deque (array-backed)
O(1)*
add to last index of Deque (array-backed)
O(1)
remove from first index of Deque (array-backed)
O(1)
remove from last index of Deque (array-backed)
O(n)
resize Deque (array-backed)
O(n)
add to BST
O(n)
search in BST
O(n)
remove from BST
O(logn)*
add to Heap
O(logn)
remove from Heap
O(n)
add to HashMap with External Chaining
O(n)
search in HashMap with External Chaining
O(n)
remove from HashMap with External Chaining
O(n^2)
add to HashMap with Linear/Quadratic Probing
O(n)
search in HashMap with Linear/Quadratic Probing
O(n)
remove from HashMap with Linear/Quadratic Probing
O(logn)
add to AVL
O(logn)
search in AVL
O(logn)
remove from AVL
O(n)
add to SkipList
O(n)
search in SkipList
O(n)
remove from SkipList
O(logn)
add to 2-4 Tree
O(logn)
search in 2-4 Tree
O(logn)
remove from 2-4 Tree
O(n)
best-case of Bubble Sort
O(n^2)
worst-case of Bubble Sort
yes
Bubble Sort stable?
yes
Bubble Sort in-place?
yes
Bubble Sort adaptive?
O(n)
best-case of Insertion Sort
O(n^2)
worst-case of Insertion Sort
yes
Insertion Sort stable?
yes
Insertion Sort in-place?
yes
Insertion Sort adaptive?
O(n^2)
best-case of Selection Sort
O(n^2)
worst-case of Selection Sort
no
Selection Sort stable?
yes
Selection Sort in-place?
no
Selection Sort adaptive?
O(n)
best-case of Cocktail Shaker Sort
O(n^2)
worst-case of Cocktail Shaker Sort
yes
Cocktail Shaker Sort stable?
yes
Cocktail Shaker Sort in-place?
yes
Cocktail Shaker Sort adaptive?
O(nlogn)
best-case of Merge Sort
O(nlogn)
worst-case of Merge Sort
yes
Merge Sort stable?
no
Merge Sort in-place?
no
Merge Sort adaptive?
O(nlogn)
best-case of Quick Sort
O(n^2)
worst-case of Quick Sort
no
Quick Sort stable?