Wouldn't it still be O(total)? Or at the very least O(log total)? You have to look at all the files even if it's just to compare the hash. The size of the file doesn't matter so I think what Linus should have said was it's O(number of files) still, and maybe O(log total) in the average case. But if there are 1,000,000 files and only 2 change then I don't see how you don't have to look at all the hashes.