UIUC CS225 Data Structures Final Flashcards

Choose a study mode

Play Quiz

Study Flashcards

Spaced Repetition

Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the time complexity of inserting an element at the front of an unsorted array?

O(n)
O(log n)
O(n log n)
O(1) (correct)

What is the time complexity of removing an element from the front of an unsorted array?

O(n)
O(log n)
O(n log n)
O(1) (correct)

What is the time complexity of pushing an element onto a stack?

O(n)
O(1) (correct)
O(n log n)
O(log n)

What is the time complexity of popping an element from a stack?

O(1) (D) Signup and view all the answers

What is the time complexity of enqueueing an element into a queue?

O(1) (B) Signup and view all the answers

What is the time complexity of dequeueing an element from a queue?

O(1) (C) Signup and view all the answers

What is the time complexity of inserting an element into a binary tree (general)?

O(1) (A) Signup and view all the answers

What is the time complexity of removing an element from a binary tree (general)?

O(n) (C) Signup and view all the answers

What is the average case time complexity of inserting an element into a binary search tree?

O(log n) (A) Signup and view all the answers

What is the time complexity of finding an element in a binary search tree?

O(n) (D) Signup and view all the answers

What is the time complexity of inserting an element into an AVL tree?

O(log n) (D) Signup and view all the answers

What is the time complexity of finding an element in a hash table (with SUHA)?

O(1) (D) Signup and view all the answers

What is the time complexity of removing an element from a dictionary?

O(1) (B) Signup and view all the answers

What is the time complexity of inserting an element into a priority queue?

O(log n) (C) Signup and view all the answers

Flashcards are hidden until you start studying

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)