What does Θ(deg(u)) mean?

I have never heard this before, or maybe I have heard it in other terms?

The context is that for adjacency lists, the time to list all vertices adjacent to u is Θ(deg(u)).

Similarly, the time to determine whether (u,v)∈ E is O(deg(u)).

If the implementation of the adjacency list is an array, then I assume it would be constant time to find u in the array.

If all adjacent vertices are linked to u, then I believe it would take O(n) 开发者_运维百科time to list or find all vertices, where n is the number of adjacent vertices.

Is that essentially what Θ(deg(u)) means?

Θ(deg(u)) = Big-Theta of the degree of u = the time is tightly-bounded (bounded from above and below) by the degree of vertices. In the case of an adjacency-list representation of the graph, the degree of a vertex u is |adj[u]| the size of the list for u.

Thus, to iterate over the adjacent vertices of u by an adjacency list is tightly-bound to the number of vertices adjacent to u (algorithmic facts sound redundant sometimes, don't they?).

The difference between Big-O and Big-Theta is that Big-O is an upper bound, whereas Big-Theta states a tight bound from above and below. That is, the same expression serves as a bound, but with a different coefficient m and x0. See the family of Bachmann-Landau notations on wikipedia.

I'm pretty sure deg(u) means "the degree of u", i.e. the number of edges that contain u. In an adjacency list representation, that number will also be the size of the adjacency list for u, so iterating it requires Θ(|list|), which is Θ(deg(u)).