A high-level call-by-reference question

First, let $$H$$ be a graph represented as an array of adjacency lists say. Next, let FindDegree$$(H,y)$$ be a standard subroutine that takes $$H$$ and a vertex $$y$$ in $$H$$ as input, and that returns the degree $$d_H(y)$$ of $$y$$ in $$H$$ as output. I am writing pseudocode that does the following: The subroutine FindDegree$$(H,y_k)$$; $$k=1,\ldots, r$$; is called by the pseudocode for $$r$$ arbitrary vertices $$y_1,\ldots, y_r$$ in $$H$$ [the graph $$H$$ is the same for all $$r$$ calls however]. I'd like to say that the total work done by these $$r$$ calls of FindDegree is only $$O(|H|+\sum_{k=1}^r d_H(y))$$ word steps as opposed to [good grief] $$\theta(r|H|)$$ word steps. Is this a reasonable assumption on my part? Does call-by-reference in say C support this? [Here the $$O$$-notation is allowed to hide polylogarithmic factors in $$|H|$$.]

As far as context, I am writing pseudocode that takes as input a large graph $$H$$, and that makes several calls to subroutines that each use, to put informally, only a small part of $$H$$ i.e., the structure of the neighborhood of a vertex in $$H$$.

• I'm not sure what a "word step" is. I have just read it as "time" or "[elementary] steps". The somewhat standard notation to hide polylogarithmic factors is $\widetilde{O}$. Nov 30, 2021 at 21:23

1 Answer

What you say is correct. In fact the total time spent by all the FindDegree calls is $$O(\sum_{k=1}^r d_H(y_k))$$ (the additional $$O(|H|)$$ time is probably spent by the rest of the algorithm to read the graph and store it into the array of adjacency lists).

You can do what you suggest in $$C$$ by passing a pointer to the array of lists (C doesn't have references). Besides, if loaded the graph into adjacency lists, don't you immediately know each vertex's degree (in constant time)? That's just the list size. Either you already have that information in your list implementation, or it can be easily maintained as satellite data.