- We discussed two implementations for a graph: adjacency list and
adjacenty matrix. Fill in the table below to give the worst-case
big-O complexity (in
terms of |V| and |E|)
of each operation for each implementation.
**Operation****Adjacency list****Adjacency matrix**Is v1 adjacent to v2? For a single vertex, find all vertices adjacent to that vertex For each vertex, find all vertices adjacent to that vertex Total space required. - Below is the generic code we discussed for a graph traversal.
If the collection is a stack, it's a DFS; if it's a queue, it's a BFS.
In terms of |V| and |E|, what is the big-O
complexity of this code assuming the graph is represented with
- an adjacency matrix?
- an adjacency list?

-- mark all vertices as unvisited -- insert the start vertex into an empty collection C -- while (C not empty) - remove a vertex v from C - if v has not been visited * visit v * insert all univisted adjacent nodes to v into C

- In big-O, how long does it take in the worst case to build an N-element
heap top-down, that is, by repeated
insertion? Explain.
- In big-O, how long does it take in the worst case to build an N-element heap bottom-up, that is,
starting at the leaves? Explain.
- Suppose you wanted to remove an arbitrary element from an N-element heap.
- Devise an algorithm for this that includes finding the element to remove.
- What is the worst-case big-O complexity of this algorithm? Explain.

- Suppose you want to build a map containing N elements and plan to use a hash table (with bucket hashing) to implement it. John says the lookup method is O(1); Mary says it is O(N). Who is correct? Explain.