Count of unread events is simple: it can be done by calculating the position of my own read receipt in the timeline (O(log|timeline|)).

Count of unread notifications is more complicated: not every unread event has a notification. We probably need to track the notifications themselves. Then counting is O(1). For updating,

• if we are to add notifications to the list (AddNotif), we need at least O(|newEvents|) calls of shouldNotify().
  • If we implement the list as flex_vector, it may also insert in the middle, so the insertion takes at most O(|newEvents| log|notif|) time.
  • If we implement the list as a map, the insertion takes at most O(|newEvents|) time.
• if we are to remove notifications (RemoveNotif) because they are already read, we need to compare the events in notifications with the read receipt. Each comparison takes O(1).
  • If we implement the list as a flex_vector, then we only need to find out the cut point before which the events are older than the read marker - this is a binary search - this means O(log|notif|) comparisons.
  • If we implement the list as a map, then we need to compare every event id with the read receipt. This means O(|notif|) comparisons.

Which of the two is more important to be efficient? AddNotif would be done more frequently (because it is done on each sync, and RemoveNotif can also be done for each sync, but only when my own read receipt has changed). But on the other hand, unread notifications (|notif|) should be sparse.