What is the proper runtime for visiting all outgoing edges in an adjacency list?

Suppose that we have a directed graph $G = (V, E)$ represented as an adjacency list. Suppose that we want to list all of the edges incident to some node $v \in V$. We can do this by iterating over all the elements in the adjacency list.

My question concerns the runtime of this operation. Is it proper to say that the runtime is $\Theta(deg^+(v))$ (since the runtime is a linear function of the outdegree of $v$)? Or should it be $\Theta(1 + deg^+(v))$, since even if $deg^+(v)$ is zero, there is some amount of work that's still done? Or are both of these terminologies incorrect because there is no underlying variable $n$ for which we could apply the formal definition of $\Theta$?

Thanks!

You're right that $\Theta(\deg^+ v)$ is a bit sloppy, but it is usually understood that $\Theta(\deg^+ v)$ is actually $\Theta(1 + \deg^+ v)$. Perhaps it's better to use the more accurate $\Theta(1 + \deg^+ v)$.

You're also right that more formally a $\Theta(\cdot)$ notation should state the underlying variable, but here there is only one variable and so no confusion can arise. Also, since $\deg^+ v$ is always non-negative, the simpler definition of $\Theta(\deg^+ v)$ - there exists $C > 0$ such that the running time is at most $C \deg^+ v$ - is unambiguous. That's also how we should understand expressions like $\Theta(n + m)$, where the two variables $n,m$ are independent.

StackExchange Computer Science Q#12959, answer score: 4