0
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ 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}$. $\endgroup$
    – Steven
    Nov 30, 2021 at 21:23

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.