On Wed, Nov 20, 2013 at 6:30 PM, Matthew Knepley <knep...@gmail.com> wrote: > On Wed, Nov 20, 2013 at 7:22 PM, Geoffrey Irving <irv...@naml.us> wrote: >> >> Was there any particular reason for making DMPlexMarkBoundaryFaces a >> quadratic time algorithm? I realize it's hard to write a subquadratic >> time algorithm on top of DMLabelSetValue; maybe PETSc needs some basic >> integer hash tables? > > Why is it quadratic time? I just looked again, and it seems to be linear > time to me.
It calls DMLabelSetValue for each boundary face. Each call to DMLabelSetValue seems to be O(log n) if the value is already set (binary search) and O(n/2) if the value is missing, since it does a PetscMemmove to shift roughly half the existing values over by one in order to insert the new entry in the middle of a sorted list. Geoffrey
