1.
(a) Theta(n), since you have to scan one entire row of a nxn matrix.
(b) Theta(k), since you have to walk through the adjacency list for v,
which is of length k.


2.
(a) n(n-1)/2
We are calculating the number of ways to pick two vertices from a
list of n.  The order of the two vertices does not matter (the edge
(u,v) is the same as the edge (v,u) in an undirected graph), so the
answer is "n choose 2", i.e., n(n-1)/2.
(b) n-1
For instance, think of a line of vertices.