1
$\begingroup$

The following algorithm for computing the number of nodes in a linked list appears in this thesis on common algorithms in the PRAM model for parallel computation.

PRAM LL Node count

The author then argues that this is a $log(n)$ time algorithm (where $n$ is the number of nodes in the list) because the span of nodes covered by the "far" pointer doubles on every iteration of the innermost loop. What I don't understand is why the author doesn't seem to factor in the time required for the first two lines of code after the begin statement, where a processor is assigned to each node in the list. Assuming the input to the algorithm is just a pointer to the header node to the linked list, wouldn't the assignment of processors require traversing each node in the linked list and thus take time linear in $n$? After all, each node in the linked list may be stored in some highly non-contiguous locations in memory identifiable only by following the chain of pointers from predecessor nodes in the list one at a time.

$\endgroup$

1 Answer 1

1
$\begingroup$

It seems this paper, which serves as a foundation for subsequent work on list ranking parallel algorithms, handles the oversight of assigning processors by assuming that the input is just given as an array containing the linked list (not necessarily in the order of the nodes in the list). This assumption of contiguous memory storage is implicitly followed in later papers such as this one.

$\endgroup$

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