Performance analysis on startDate and endDate on OCKSchedule

[vanvoorden]

Hi! I'm a little curious about the runtime and space complexity performance of startDate() and endDate() on OCKSchedule.¹

Why must we perform O(n log n) work to return the minimum Date? And why must we create O(n) additional storage?

Could startDate() and endDate() both be refactored to return in O(n) time and O(1) space?

What about something like:

public func startDate() -> Date {
  var earliestStartDate: Date? = nil
  for e in elements {
    if let d = earliestStartDate {
      if e.start < d {
        earliestStartDate = e.start
      }
    } else {
      earliestStartDate = e.start
    }
  }
  guard let earliestStartDate = earliestStartDate
  else { fatalError("OCKSchedule should always have at least 1 element!") }
  return earliestStartDate
}

And then something similar for endDate()?

Footnotes

1. https://github.com/carekit-apple/CareKit/blob/4.1.0/CareKitStore/CareKitStore/Structs/OCKSchedule.swift#L64-L82 ↩