CODEWITHSUNDEEP
haskelltime-complexity
erewok
erewok

Reputation: 7835

Time Complexity for index and drop of first item in Data.Sequence

I was recently working on an implementation of calculating moving average from a stream of input, using Data.Sequence. I figured I could get the whole operation to be O(n) by using a deque.

My first attempt was (in my opinion) a bit more straightforward to read, but not a true a deque. It looked like:

  let newsequence = (|>) sequence n
  ...
  let dropFrontTotal = fromIntegral (newtotal - index newsequence 0)
  let newsequence' = drop 1 newsequence. 
  ...

According to the hackage docs for Data.Sequence, index should take O(log(min(i,n-i))) while drop should also take O(log(min(i,n-i))).

Here's my question:

If I do drop 1 someSequence, doesn't this mean a time complexity of O(log(min(1, (length someSequence)))), which in this case means: O(log(1))?

If so, isn't O(log(1)) effectively constant?

I had the same question for index someSequence 0: shouldn't that operation end up being O(log(0))?

Ultimately, I had enough doubts about my understanding that I resorted to using Criterion to benchmark the two implementations to prove that the index/drop version is slower (and the amount it's slower by grows with the input). The informal results on my machine can be seen at the linked gist.

I still don't really understand how to calculate time complexity for these operations, though, and I would appreciate any clarification anyone can provide.

Upvotes: 1

Views: 349

Answers (1)

chi
chi

Reputation: 116139

What you suggest looks correct to me.

As a minor caveat remember that these are amortized complexity bounds, so a single operation could require more than constant time, but a long chain of operations will only require a constant times the number of the chain.

If you use criterion to benchmark and "reset" the state at every computation, you might see non-constant time costs, because the "reset" is preventing the amortization. It really depends on how you perform the test. If you start from a sequence an perform a long chain of operations on that, it should be OK. If you repeat many times a single operation using the same operands, then it could be not OK.

Further, I guess bounds such as O(log(...)) should actually be read as O(log(1 + ...)) -- you can't realistically have O(log(1)) = O(0) or, worse O(log(0))= O(-inf) as a complexity bound.

Upvotes: 2

Related Questions