FINAL EXAM ESSENTIALS ONLY MEMORIZATION
Studied by 0 people
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt Play1/50
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced |
|---|
No study sessions yet.
51 Terms
Big O definition
The upper bound on time or space as input grows
O(1)
Constant time
O(n)
Linear time
O(n log n)
Efficient sorting complexity (merge and quick average)
O(log n)
Logarithmic time (binary search)
Binary search complexity
O(log n)
Array indexing
O(1)
Array insert/delete
O(n)
Vector push_back amortized
O(1)
Vector resize
O(n)
Linked list insert head
O(1)
Linked list search
O(n)
Stack push/pop
O(1)
Queue enqueue/dequeue
O(1)
Tree traversal complexity
O(n)
Preorder traversal
Root, Left, Right
Inorder traversal
Left, Root, Right
Postorder traversal
Left, Right, Root
Level order traversal
Uses queue
BST property
Left < root < right
BST search avg
O(log n)
BST search worst
O(n)
Heap insert
O(log n)
Heap remove-min
O(log n)
Heap find-min
O(1)
Hash table average search
O(1)
Hash table worst-case
O(n)
Collision handling methods
Chaining, open addressing
Load factor
Number of elements / table size
BFS uses
Queue
DFS uses
Stack or recursion
BFS complexity
O(V + E)
DFS complexity
O(V + E)
Bubble sort
O(n^2)
Selection sort
O(n^2)
Insertion sort
O(n^2)
Merge sort
O(n log n)
Quick sort avg
O(n log n)
Quick sort worst
O(n^2)
Pointer definition
Variable storing a memory address
new operator
Allocates dynamic memory
delete operator
Releases dynamic memory
Dangling pointer
Pointer to freed memory
nullptr
Represents empty pointer safely
ADT definition
Abstract Data Type
Complete binary tree
Levels filled left to right
Full binary tree
Nodes have 0 or 2 children
Queue definition
FIFO
Stack definition
LIFO
Graph adjacency list
List of neighbors per vertex
Graph adjacency matrix
VxV grid of edges
Note 
Flashcards (24)