Practice with Complexity Analysis

1. 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.

2. 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
   1. an adjacency matrix?
   2. an adjacency list?
   Explain your answers.

     -- 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
   

3. 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.

4. 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.

5. Suppose you wanted to remove an arbitrary element from an N-element heap.
   1. Devise an algorithm for this that includes finding the element to remove.
   2. What is the worst-case big-O complexity of this algorithm? Explain.

6. 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.