10 Data Structure and Algorithm Trade-offs Free Online FlashCards

What factors guide data-structure selection?

Choose a structure by considering required operations, their frequency, data properties, memory and locality, correctness constraints, and maintainability.

What are key dynamic-array operation costs?

A dynamic array provides $O(1)$ indexing and amortized $O(1)$ appending, but insertion or deletion in the middle is $O(n)$ because elements move.

What is linked-list access time by position?

Accessing position $i$ in a linked list is $O(n)$, because nodes must be followed sequentially from a known starting point.

What processing order does a stack enforce?

A stack follows last-in, first-out order: `push` adds an item, `pop` removes the newest item, and `peek` inspects it.

What processing order does a queue enforce?

A queue follows first-in, first-out order: `enqueue` adds at the rear, while `dequeue` removes the oldest item from the front.

How does balance affect BST operation costs?

A balanced BST typically supports search, insertion, and deletion in $O(\log n)$; an unbalanced BST can degrade to $O(n)$.

What is the typical hash-table complexity profile?

A hash table offers expected $O(1)$ exact-key lookup, insertion, and deletion with a good hash function and controlled load factor, but its worst case is $O(n)$.

What is binary search’s comparison complexity?

Binary search takes $O(\log n)$ comparisons by repeatedly halving a sorted search interval.

What trade-off does a sorted array create?

A sorted array combines $O(\log n)$ binary search with $O(n)$ insertion, because inserting at the correct position moves elements.

What distinguishes merge sort?

Merge sort has $O(n\log n)$ worst-case time, is stable, and suits linked lists or external data; typical array implementations need extra storage.

What three elements make recursion correct?

A recursive function needs a base case, progress toward that case, and a way to combine recursive results.

What is the total cost of sorting once and doing $m$ binary searches?

The total is $O(n\log n+m\log n)$: $O(n\log n)$ to sort once plus $O(m\log n)$ for $m$ binary searches.