4 of 7 added 80 characters in body

Using complement operation 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;
}