The company would likely require explicit consent for using facial recognition algorithms.
The GPDR considers certain activities to be processing of “special categories” of personal data (Art 9 GDPR). One of these categories is “biometric data for the purpose of uniquely identifying a natural person”. Such processing activities are prohibited unless an exception applies.
Facial recognition uses biometrics to identify a person, so it's prohibited by default.
There are, of course, many exceptions. Art 9(2) GDPR contains a list of general exceptions which allow special categories data to be processed. In UK law, specific conditions for these situations are given in Schedule 1 of the Data Protection Act 2018. Whether any exception could apply depends a lot on the purpose for applying facial recognition, e.g. if it is necessary in a medical context or if it is truly necessary in an employment context.
The most interesting exception in the context of video surveillance would be Art 9(2)(f):
processing is necessary for the establishment, exercise or defence of legal claims
However, necessity is a fairly high bar to clear. This exception cannot be used to pre-emptively scan a database of images in the hopes that it might find something. In contrast, it might be permissible to use facial recognition to confirm a suspicion. But here, there's a big caveat in that most facial recognition software cannot provide reliable results for less than ideal pictures (i.e. anything other than a well-lit frontal portrait of the face), and that such software is known to produce biased results. Thus, the use of facial recognition by private companies is still questionable.
If none of the exemptions in the GDPR/DPA clearly applies, then only the Art 9(2)(a) exception is left over:
the data subject has given explicit consent to the processing of those personal data for one or more specified purposes
A notable example of a company illegally performing facial recognition is Clearview AI. Multiple data protection authorities have announced fines, including the UK's ICO: in late 2021, the ICO announced the intent to issue a GBP 17M fine for, among other things, failing to meet the higher data protection standards required for biometric data.
This answer applies to private-sector data controllers, i.e. ordinary companies. Different rules can apply in the public sector, in particular for law enforcement agencies.