Using [complement operation][1] from set theory. 
And assuming recent notifications limited to 100.

    Set<Notification> updateNotifications(Set<Notification> persisted, Set<Notification> recent) {
        Set<Notification> newNotifications = complement(recent, persisted);
        save(newNotifications);
        persisted = persisted.addAll(newNotifications);

        if (persisted.size() <= 100) {
            return persisted;
        }
    
        Set<Notification> obsoleteNotifications = complement(persisted, recent);
        delete(obsoleteNotifications);
        persisted = persisted.removeAll(obsoleteNotifications);
    
        return persisted;
    }


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