title: Time Complexity for index and drop of first item in Data.Sequence
body: <p>I was recently working on an implementation of <a href="https://gist.github.com/pellagic-puffbomb/9239cb57834789886f5c" rel="nofollow noreferrer">calculating moving average from a stream of input</a>, using <code>Data.Sequence</code>. I figured I could get the whole operation to be O(n) by using a deque.</p>
  <p>My first attempt was (in my opinion) a bit more straightforward to read, but not a true a deque. It looked like:</p>
  <pre><code>  let newsequence = (|&gt;) sequence n
    ...
    let dropFrontTotal = fromIntegral (newtotal - index newsequence 0)
    let newsequence' = drop 1 newsequence. 
    ...
  </code></pre>
  <p>According to the <a href="https://hackage.haskell.org/package/containers-0.5.6.3/docs/Data-Sequence.html#g:11" rel="nofollow noreferrer">hackage docs</a> for <code>Data.Sequence</code>, <code>index</code> should take <em>O(log(min(i,n-i)))</em> while <code>drop</code> should also take <em>O(log(min(i,n-i)))</em>.</p>
  <p><strong>Here's my question:</strong></p>
  <p>If I do <code>drop 1 someSequence</code>, doesn't this mean a time complexity of <em>O(log(min(1, (length someSequence))))</em>, which in this case means: <em>O(log(1))</em>?</p>
  <p>If so, isn't <em>O(log(1))</em> <em>effectively</em> constant?</p>
  <p>I had the same question for <code>index someSequence 0</code>: shouldn't that operation end up being <em>O(log(0))</em>?</p>
  <p>Ultimately, I had enough doubts about my understanding that I resorted to using <code>Criterion</code> to benchmark the two implementations to prove that the <code>index/drop</code> 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.</p>
  <p>I still don't really understand how to calculate time complexity for these operations, though, and I would appreciate any clarification anyone can provide.</p>