Data Structures and Algorithms: Time Complexities for Arrays, Linked Lists, Stacks, Queues, and Hash Tables

What is the worst-case time complexity for inserting into an unordered array?

O(1) (amortized)

What is the worst-case time complexity for finding an element in an unordered array?

O(n)

What is the time complexity for deleting an element from an unordered array?

O(n)

Why is array insertion marked as O(1) (amortized)?

Because actual insertion is O(1), but resizing or finding the position can take longer.

What is the time complexity of inserting at the head of a singly linked list?

O(1)

What is the time complexity of inserting at the tail of a singly linked list (with tail pointer)?

O(1)

What is the time complexity of finding an element in a singly linked list?

O(n)

What is the time complexity of deleting an element in a singly linked list?

O(n)

What is the time complexity of insertion in an ordered array (linear search)?

O(n)

What is the time complexity of searching in an ordered array using linear search?

O(n)

What is the time complexity of searching in an ordered array using binary search?

O(log n)

What is the time complexity of deletion in an ordered array?

O(n)

What is the time complexity of insertion in an ordered singly or doubly linked list?

O(n)

What is the time complexity of searching in an ordered linked list?

O(n)

What is the time complexity of push, pop, and peek in an array-based stack?

O(1) (push is amortized O(1))

What is the time complexity of push, pop, and peek in a linked-list-based stack?

O(1)

Why is stack not created for searching?

Because stacks are LIFO — only top access is allowed.

What is the enqueue complexity for an array-based queue?

O(1) (amortized)

What is the dequeue complexity for an array-based queue?

O(n)

What is the enqueue and dequeue complexity for a circular array queue?

O(1)

What is the enqueue and dequeue complexity for a linked-list-based queue (with tail pointer)?

O(1)

What is the dequeue complexity for a linked-list-based queue (without tail pointer)?

O(1)

What is the time complexity of hash table insert/find/delete (average case)?

O(1)

What is the time complexity of hash table insert/find/delete (worst case)?

O(n)

What algorithm is reminiscent of BFS, but adapted to handle weights?

Dijkstra's Algorithm

What does Dijkstra's Algorithm do?

Find the single-source shortest paths in a weighted graph

What causes an error in Dijkstra's algorithm?

negative-weight edges

In Dijkstra's Algorithm, what is better for a sparse graph?

Priority Queue, O(|V|log|V| + |E|log|V|)

In Dijkstra's Algorithm, what is better for a dense graph?

O(|V|^2)

What algorithm's idea is to grow a forest of edges that does not form a cycle but also considers the edges in order by weight?

Kruskal's Algorithm

What algorithm's idea is to grow a tree by adding an edge from the "known" vertices to the "unknown" vertices, picking the edge with the smallest weight that connects "known" to "unknown."

Prim's Algorithm

What is the run time for Prim's?

O(|E|log|V|) (same as Dijkstra)

What is the time complexity of Kruskals?

O(ElogV)​

Adjacency Matrix or List, which is better for dense graphs?

Adjacency Matrix

Adjacency Matrix or List, which is better for sparse graphs?

Adjacency List, so usually just stick with linked list

What algorithm is used for a DAG, so that no vertex appears before another vertex?

Topological Sort

What is the worst case run time for topo sort?

O(|E| + |V|) so if dense then O(|V|^2)

What is the worst-case time complexity of union find with path compression?

O(m a(n))​