Missing numbers in a sequence

4

I’d like to once again reiterate on what I tried to teach you just a few days ago.

Do the answers above work? Yes, absolutely.
Are they the most optimal? Not always.
Is this a problem for short sequences? Not at all, but it’s still a good exercise to try and find an alternative solution that could be better in certain situations.

What the above algorithm does:

  • For each of N items
    • Check if the data set contains that item (by performing at least one, at most N checks of the item against each item from the set)

Therefore the complexity is O(N^2), i.e. the larger is the sequence, the more time it would take quadratically to calculate this. I.e. twice the numbers would take 4 times longer to calculate, 4 times the numbers would take 16x longer and so on.

Since the incoming dataset is already sorted, we could optimize the algorithm by only comparing N+1th with the Nth item and collecting the missing numbers between. The algorithm is more complicated and most likely will take longer time to calculate on small data sets, but on larger datasets it would win because it is linear, i.e. the number of operations (checks or additions to the list) and the time to calculate would grow proportionately to the number of items, i.e. 4 times the items would take not 16x the time but only 4x the time.

Sequence(2, Items.Count()).FormulaMap(
  If(
    Items.Nth(CurrentValue) - Items.Nth(CurrentValue - 1) != 1,
    Sequence(Items.Nth(CurrentValue - 1) + 1, Items.Nth(CurrentValue) - 1),
    List()
  )
).ListCombine()

I guess it’s time to record my own course on Coda performance and optimizations. Who’d like one?

6 Likes