Data Structures Time Complexities - Comp 210
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt Play1/28
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai |
|---|
No analytics yet
Send a link to your students to track their progress
29 Terms
Unsorted ArrayList Access: Best/Avg/Worst
O(1)
Unsorted ArrayList Search: Best, Avg,Worst
O(1), O(N)
Unsorted ArrayList Insert (end): Best/Avg, Worst (resize)
O(1), O(N)
Unsorted ArrayList Insert (anywhere)
O(N)
Unsorted ArrayList Delete
O(N)
Sorted ArrayList Access
O(1)
Sorted ArrayList Search (binary search): Best, Avg/Worst
O(1), O(logN)
Sorted ArrayList Insert (shifting elements)
O(N)
Sorted ArrayList Delete
O(N)
Unsorted Linked List Access
O(N)
Unsorted Linked List Search: Best, Avg/Worst
O(1), O(N)
Unsorted Linked List Insert (head)
O(1)
Unsorted Linked List Insert (tail)
O(1) (if tail pointer)
Unsorted Linked List Delete
O(N) (need to find node)
Sorted Linked List Access
O(N)
Sorted Linked List Search: Best, Avg/Worst
O(1), O(N)
Sorted Linked List Insert
O(N) (must find correct spot)
Sorted Linked List Delete
O(N)
Heap Access (top element)
O(1)
Heap Search
O(N)
Heap Insert: Best, Avg/Worst
O(1), O(logN)
Heap Delete (root)
O(logN)
Balanced BST Access
O(logN)
Balanced BST Search: Best, Avg/Worst
O(1), O(logN)
Balanced BST Insert
O(logN)
Balanced BST Delete
O(logN)
Hashtable (with resizing, probing) Search: Best, Avg, Worst
Best O(1), Avg O(1), Worst O(n)
Hashtable (with resizing, probing) Insert: Best, Avg, Worst (resize or clustering)
Best O(1), Avg O(1), Worst O(n) (resize or clustering)
Hashtable (with resizing, probing) Delete: Best, Avg, Worst
Best O(1), Avg O(1), Worst O(n)