If you're looking in a list of files it's going to be an O algorithm. That's the way application theming is done at any level. The results that TheSpaz is getting do nothing but verify this. This would also probably be why ShapeShifter keeps a plist of files for the current theme, or why when you do an fs_usage you can see ShapeShifter redirecting the file opens, or why ShapeShifter is still writing out all the files from a theme individually, or why ShapeShifter has to reapply on a system update, or why ShapeShifter has to reapply when iTunes is updated... Either that or ShapeShifter keeps the plist for no clear reason, and all paths are hardcoded (which in itself could still be considered an O search algorithm), but I doubt that. I don't think ShapeShifter's fsref overrides are just for fun.

If you're catching a resource fetch mid call and pulling from another open resource file, yes, that's going to be a constant. That still doesn't change that for any application skin, even if the system is just running opens that have nothing to do with themes, you're going to take an O level hit. An O level hit doesn't refer to the average speed hit, it refers to the maximum. At maximum, you could take a speed hit that is dependent on how many files you are theming.