Thực ra đúng phải là khi sử dụng KEYS để tìm kiếm keys thỏa mãn theo một pattern (matching pattern) thì độ phức tạp là O(n).

Có lẽ câu từ khiến bạn bị hiểu nhầm.