Data Structures Midterm

Worst-case time complexity

Maximum time an operation can take for input size n.

Average-case time complexity

Expected time over an assumed distribution of inputs or tree shapes.

Amortized time complexity

Average cost per operation over a sequence of operations, even if some operations are expensive.

Primitive operation (POP)

An elementary operation counted in algorithm analysis: assignment, function call, arithmetic, comparison, Boolean operation, indexing/pointer traversal, or return.

Big-O notation

Asymptotic upper bound on an algorithm's growth rate.

Hash table load factor

λ = n/N, where n is the number of entries and N is table capacity.

Hash function

Maps a key to an integer hash code.

Compression function

Maps a hash code to a valid table index.

Polynomial hash method

Weights character positions when calculating a string's hash code, so different character orders can produce different codes.

MAD compression method

Multiply-Add-Divide: maps a hash code to an index using multiplication, addition, and modulo by table capacity.

Hash table: Clear

Average O(n); worst-case O(n).

Hash table: Get

Average O(1); worst-case O(n).

Hash table: Put

Average O(1); worst-case O(n).

Hash table: Remove

Average O(1); worst-case O(n).

Hash table: Replace

Average O(1); worst-case O(n).

Hash table: ChangeCapacity

O(n) average and worst case.

Hash table: Rehash

O(n) average and worst case.

BST: Clear

O(n) average and worst case.

BST: Find

Average O(log n); worst-case O(n).

BST: Height

Average O(log n); worst-case O(n).

BST: Insert

Average O(log n); worst-case O(n).

BST: Remove

Average O(log n); worst-case O(n).

BST: Copy

O(n) average and worst case.

BST: Preorder to List

O(n) average and worst case.

B-Tree: Clear

O(n) average and worst case.

B-Tree: Find

O(log_t n) average and worst case.

B-Tree: Height

O(log_t n) average and worst case.

B-Tree: Insert

O(log_t n) average and worst case.

B-Tree: Remove

O(log_t n) average and worst case.

Hash table expected operation time

O(1), assuming a suitable hash function and reasonable load factor.

Hash table worst-case operation time

O(n), when many keys collide or the table must be scanned.

BST worst-case operation time

O(n), when the tree degenerates into a chain.

B-Tree operation time

O(log_t n), where t is the minimum degree/order parameter.

Effect of increasing B-Tree t

A larger t can reduce tree height and the number of levels traversed.

Separate chaining recommended load factor

λ < 0.9, according to the study notes.

Open addressing recommended load factor

λ < 0.5, according to the study notes.

Propositions 4.3, 4.5, 4.9, 10.7, 10.8, 14.1 and Theorem 18.1

4.3: 1+...+n=n(n+1)/2, useful for O(n²) nested loops. 4.5: geometric sum=(a^(n+1)-1)/(a-1), for a≠1. 4.9: degree-d polynomial is O(n^d). 10.7: n-entry multi-way search tree has n+1 external nodes. 10.8: (2,4)-tree height is O(log n), so operations are O(log n). 14.1: (a,b)-tree height is logarithmic in n. 18.1: B-Tree find, insert and remove are O(log_t n).

Hash table load factor formula

λ = n/N, where n is entries and N is capacity.

Separate chaining

Stores colliding entries in a collection, such as a linked list, at the same bucket.

Open addressing

Stores entries directly in the table and probes for another slot after a collision.

Closed addressing

Another name used in the notes for separate chaining.

Collision

Occurs when multiple keys map to the same table index.

Linear probing

After a collision, check successive table positions, wrapping around at the end.

Quadratic probing

Checks positions A[(i+j²) mod N] for j=0,1,2,...

Quadratic probing limitation

May cause clustering and may fail to visit every slot under unsuitable table-size conditions.

Double hashing

Uses a second hash function to determine the probe step after a collision.

Double hashing probe formula

A[(i+f(j)) mod N], where f(j)=j×c(h'(k)) in the notes.

Secondary hash function requirement

The secondary hash must not produce a zero step size.

Example secondary hash function

c(h(k)) = q − (h(k) mod q), according to the notes.

Purpose of rehashing

Recompute bucket positions for existing entries after table capacity changes.

Hash table resizing and amortized analysis

A resize costs O(n), but infrequent geometric resizing can make amortized insertion O(1).

BST ordering property

Every key in a node's left subtree is smaller; every key in its right subtree is greater.

BST search rule

If the target is smaller, go left; if greater, go right; if equal, return the node.

BST insertion rule

Follow the ordering property until reaching an empty child position, then insert.

BST removal with two children

Replace the removed key with the minimum key in its right subtree, then remove that successor.

BST typical search time

O(log n) for a suitably shaped tree.

BST worst-case search time

O(n) when the tree degenerates into a chain.

Ancestor

Node u is an ancestor of v if u=v or u is an ancestor of v's parent.

Descendant

Node v is a descendant of u if u is an ancestor of v.

Is a node its own ancestor?

Yes, according to the notes' definition.

Is a node its own descendant?

Yes, according to the notes' definition.

Depth of a node

Number of ancestors, excluding the node itself.

Height of a tree

Maximum node depth; equivalently, the number of edges on the longest root-to-leaf path.

Height of an external node

0, according to the notes.

External nodes in a BST

Represented by null pointers.

External nodes in a B-Tree

Represent actual external positions rather than null pointers, according to the notes.

Preorder traversal

Visit root, traverse left subtree, then right subtree.

Inorder traversal

Traverse left subtree, visit root, then traverse right subtree.

Postorder traversal

Traverse left subtree, traverse right subtree, then visit root.

Level-order traversal

Visit nodes level by level, typically using a queue.

Depth-first search (DFS)

Explores deeply before backtracking; typically uses a stack or recursion.

Breadth-first search (BFS)

Explores level by level; typically uses a queue.

(a,b)-tree size property

Each internal node other than the root has at least a children; every internal node has at most b children.

(a,b)-tree depth property

All external nodes have the same depth, so the tree is balanced.

B-Tree minimum degree t

Parameter determining the minimum number of keys and children allowed in non-root nodes.

B-Tree minimum keys per non-root node

t−1 keys.

B-Tree maximum keys per node

2t−1 keys in the standard minimum-degree convention.

B-Tree minimum children per non-root internal node

t children.

B-Tree maximum children per internal node

2t children in the standard minimum-degree convention.

B-Tree root key property

The root has at least one key when the tree is nonempty.

B-Tree height

O(log_t n).

B-Tree find

O(log_t n).

B-Tree insert

O(log_t n).

B-Tree remove

O(log_t n).

B-Tree split during insertion

Split a full node and promote its median key to the parent.

B-Tree borrowing during deletion

Transfer a key through the parent from a sibling with an extra key.

B-Tree merging during deletion

Combine a child, a separator key from the parent, and a sibling when borrowing is unavailable.

B-Tree root contraction

If deletion leaves the root empty with one child, make that child the new root.

How to calculate f(n)

Count primitive operations as a function of input size n.

How to determine Big-O from f(n)

Identify the dominant growth term; ignore constant factors and lower-order terms.

Single loop running n times

O(n), assuming constant work per iteration.

Two nested loops each running n times

O(n²), assuming constant work per iteration.

Three nested loops each running n times

O(n³), assuming constant work per iteration.

Sequential loops

Add their costs; the dominant term determines the overall Big-O.

Triangular nested-loop iteration count

1+2+...+n=n(n+1)/2, giving O(n²).

Loop that doubles its variable each iteration

O(log n), when doubling until reaching n.

Array indexing

One primitive operation under the notes' counting model.

Pointer traversal

One primitive operation under the notes' counting model.

Assignment

One primitive operation under the notes' counting model.

Arithmetic operation

One primitive operation under the notes' counting model.