You might use [set operations][1]: complement and union.

Assuming that recent notifications limited to 100.

    Set<Id> updateNotifications(Set<Id> persisted, Set<Id> recent) {
        Set<Id> newNotifications = complement(recent, persisted);
        save(newNotifications);
    
        if (recent.size() < 100) {
            return union(persisted, newNotifications);
        }
    
        Set<Id> obsoleteNotifications = complement(persisted, recent);
        delete(obsoleteNotifications);
    
        return newNotifications;
    }


  [1]: https://en.wikipedia.org/wiki/Set_(mathematics)#Basic_operations