In this lecture, we'll complete
our algorithm analysis for our graph and graph node classes.
We'll start by analyzing the complexity of the GraphNode operations.
So, we'll scroll down to adding a neighbor.
The neighborsContains method which is a list method is order n,
where n is the number of items in the list.
This is constant time.
Adding a neighbor is either order one if we don't have to expand the list,
or order n if we do have to expand the list.
And this is constant time.
But this we know is always order n. So,
the AddNeighbor operation is order n,
where n is defined as the number of neighbors for the node.
Removing a neighbor is also order n because the list remove
method is order n. It does a linear search to find the neighbor to remove,
so in the worst case it goes all the way to the end before finding the neighbor,
or not finding the neighbor.
So, the Remove method is an order n method.
So, the RemoveNeighbor operation for GraphNode is also order n.
Removing all neighbors is order n.
The RemoveAt method because we're removing from the end of the list,
I've written this for loop to go backwards not forwards,
so we're removing from the end of the list each time,
and that's a constant time operation because nothing in
the list has to get shifted around once we remove the GraphNode.
So, the body of the loop is order one,
but this for loop executes n times.
So, the RemoveAllNeighbors operation is
order n because we need to remove each of those neighbors,
so it's a order n, where n is defined as the number of neighbors.
The ToString method is also order n,
where n is the number of neighbors because of this for loop that executes n times,
once for each neighbor.
For the graph, it is common for people to specify complexities for graphs using V,
for the number of vertices in the graph and E,
for the number of edges in the graph.
So, even though we have typically been talking about order n,
where n would be say,
the number of nodes in the graph,
we'll be consistent with common convention for graphs and we'll express our complexities
in terms of V. And I'll point out
one place where E might give us a better result, when we get there.
So, we'll start with the Clear method.
The RemoveAllNeighbors method for a GraphNode is order n,
where n is the number of neighbors.
But in the worst case,
a node could be connected to all other nodes in the graph, including itself.
So, in the worst case,
n is actually V,
the number of vertices in the graph.
So, the body of this first loop is order V.
We also are going to iterate over all the vertices or nodes in the graph.
So, this outer loop is order V as well.
The way we calculate the complexity for this loop as a whole,
is we take the complexity of the loop body,
and we multiply it by the complexity of the loop itself.
And we do that because for each iteration,
we might get the worst case here.
So, this is order V,
and this is order V,
so this is actually order V squared,
V times V is V squared.
This bottom for loop,
the list RemoveAt method because we're removing from the end again,
going backwards, is constant time.
So, constant time times order V,
because this touches every vertex in the graph.
So, this loop is order V. So,
we have an order V squared loop and an order V loop,
so the complexity of the Clear operation is order V squared,
because V squared dominates V and we can just throw the V away.
Now, the worst case for removing all neighbors is
actually based on the fact that this is what's called the dense graph.
So, there are lots of edges relative to the number of nodes or vertices in the graph.
In a sparse graph,
where we have fewer edges,
this is really pessimistic because in fact,
this can't be V in the sparse graph,
it's going to be much smaller than that.
So, one other way we can think about this,
is this inner loop is order E overall.
In the worst case through all of the iterations of this outer loop,
we're going to do two E removals,
because the edge is actually contained in both nodes to connect to the other node.
So, if we want to be a little more precise,
we can say this first loop is order V times E,
instead of order V squared,
and so that's a little more fair for sparse graphs.
For the rest of our discussion here,
I'm just going to express everything in terms of V
because that is generally applicable to all graphs whether it's sparse or dense.
But you should recognize the fact that for sparse graphs,
including an E term for the number of edges in the graph can give
you a tighter upper bound on the complexity of doing stuff on the graph.
To add a node, we'll actually discover that
the Find method is order V once we go analyze that.
So, order V, constant time.
Adding to the list is either order one if we don't have to expand the list,
or order V if we do.
And then this is constant time.
So, this is clearly the dominant factor,
it's order V. So,
adding a node to the graph is order V. Adding an edge between two nodes,
I just said that the Find operation or method is order V. So,
these first two lines are order V. And then we have some constant time stuff.
And then checking a neighbor to see if that edge already exists is in fact,
order V in the worst case.
For a complete graph,
we'd have to work a list of neighbors that
contained V different entries for all the nodes in the graph.
So, this is also order V. And this is constant time.
So, we saw this before when we added a neighbor to a GraphNode.
That if we needed to expand that list of neighbors then it was order n,
where n is the number of neighbors.
And here for a complete graph or even a dense graph,
we're going to say this is order V. So,
we have a bunch of order V's but none of them are nested inside another one.
So, there's no multiplication here,
there's just a bunch of adding.
So the AddEdge operation is
order V. For the RemoveNode operation or method,
this is order V. We have a bunch of constant time stuff.
Removing an item from the list is order V because
the list Remove method does a linear search for that item to remove.
So, NodeRemoveNeighbor is order n,
where n is the number of neighbors for the node.
So, we'll say order V for a dense or complete graph.
So, the body of this loop is order V. And the loop executes V times,
one for each vertex or node in the graph.
So, we have to multiply this order V by this order V,
which tells us that the RemoveNode operation is order V squared.
Removing an edge, order V. Order V, constant time.
Order V, constant time.
Removing each neighbor is order V as well.
And because all these order V's are added together,
the RemoveEdge operation is
order V. The Find simply does a linear search of the GraphNodes.
So, this is order V because this loop executes in the worst case, the times.
And finally, converting to a string is also order V
because we convert each node in the graph to a string.
To recap, in this lecture,
we got more algorithm analysis practice.
We discovered that the complexity of algorithms
on graphs are regularly expressed using V,
the number of vertices in a graph.
And we also learned that using both V and E,
the number of edges in a graph,
can give us a tighter bound on the complexity for some algorithms on sparse graphs.
