Questions and Answers
What is the time complexity of inserting an element at the front of an unsorted array?
What is the time complexity of removing an element from the front of an unsorted array?
What is the time complexity of pushing an element onto a stack?
What is the time complexity of popping an element from a stack?
Signup and view all the answers
What is the time complexity of enqueueing an element into a queue?
Signup and view all the answers
What is the time complexity of dequeueing an element from a queue?
Signup and view all the answers
What is the time complexity of inserting an element into a binary tree (general)?
Signup and view all the answers
What is the time complexity of removing an element from a binary tree (general)?
Signup and view all the answers
What is the average case time complexity of inserting an element into a binary search tree?
Signup and view all the answers
What is the time complexity of finding an element in a binary search tree?
Signup and view all the answers
What is the time complexity of inserting an element into an AVL tree?
Signup and view all the answers
What is the time complexity of finding an element in a hash table (with SUHA)?
Signup and view all the answers
What is the time complexity of removing an element from a dictionary?
Signup and view all the answers
What is the time complexity of inserting an element into a priority queue?
Signup and view all the answers
Study Notes
Runtime Complexity for Data Structures
-
Unsorted Array Operations
- Insert at Front: O(1)
- Insert: O(n)
- Remove at Front: O(1)
-
Stack Operations
- Push: O(1)
- Pop: O(1)
-
Queue Operations
- Enqueue: O(1)
- Dequeue: O(1)
Binary Tree and Variants
-
Binary Tree (General)
- Insert: O(1)
- Remove: O(n)
- Find: O(n)
- Traverse: O(n)
-
Binary Search Tree (BST)
- Insert: O(n), average case is O(log n)
- Remove: O(n)
- Find: O(n)
- Traverse: O(n)
-
AVL Tree (Balanced BST)
- Insert: O(log n)
- Remove: O(log n)
- Find: O(log n)
- Traverse: O(n)
-
BTree
- Insert: O(log n)
- Remove: O(log n)
- Find: O(log n)
- Traverse: O(n)
- Order m characteristics: max children = m, keys per node between m/2 - 1 and m - 1 (except root)
BTree Properties
- Search Complexity: O(m) per node, O(log_m n)
- Maximum nodes: ((m^{(h + 1)} - 1) / (m - 1))
- Maximum keys: (m^{(h + 1)} - 1)
- Minimum nodes: (1 + 2 \cdot \left(\frac{t^h - 1}{t - 1}\right))
- Minimum keys: (n \geq 2 \cdot t^h - 1)
- Height: (h = O(log n))
Hash Table Operations
-
SUHA (Straight-Up Hash Array)
- Insert: O(1)
- Remove: O(1)
- Find: O(1)
- Assumes deterministic function and even distribution of keys.
- Resizing occurs when load factor (n/N) exceeds ~2/3, resizing to next prime greater than (2 * current size).
-
Separate Chaining
- Insert: O(1)
- Remove/Find (without SUHA): O(n)
- Remove/Find (with SUHA): O(load factor)
Dictionary Operations
- Insert: O(1)
- Remove: O(1)
- Find: O(1)
Priority Queue and Heap
-
Priority Queue
- Insert: O(log n)
- Remove: O(log n)
-
Heap Operations
- Insert: O(log n)
- Remove Min: O(log n)
- Heapify Up: O(log n)
- Heapify Down: O(log n)
- Build Heap: O(n) through Heapdown; O(n log n) through Heapify Up
- Height: log(n) for n nodes
-
Heap Array Relations
- Root index: i = 1
- Left Child: i = 2i
- Right Child: i = 2i + 1
- Parent: floor(i/2)
Disjoint Sets
-
Without Path Compression and Smart Union
- Find: O(n)
- Union: O(1)
-
With Smart Union
- Find: O(log n)
- Union: O(1)
-
With Path Compression and Smart Union
- Find: O(1) (worst case O(mlog n))
- Union: O(1)
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Test your knowledge of data structures with these flashcards for the UIUC CS225 final. This set covers various operations and their time complexities, focusing on arrays, stacks, and queues. Perfect for quick review and memorization before the exam.
