Newbie questions (I have searched the Internet a bit, did not find information to answer these):

I understand that anti-viruses (AVs) maintain signatures of viruses (which as I understand are byte patterns present in that virus not present in non-infected software code). They also look for executables modifying others.

Questions:

1. If AVs have to match byte patterns for a very large number of known viruses (millions??), would this not make scanning each executable very slow? This seems to be O[e*v] operation where e is the number of executables and v is the number of viruses. Since it does not seen as slow intuitively, what is going on?

2. I presume AVs would also track check-sums of known executables so that these can be safe guarded against new viruses for which signatures are not yet available. Is this right?