Time complexity of looking up in a rainbow table It is mentioned in the famous paper Making a Faster Cryptanalytic Time-Memory Trade-Off (pdf) by Philippe Oechslin that:


  The total number of calculations we have to make is thus
  $\frac{t(t−1)}{2}$. This is half as much as with the classical
  method. Indeed, we need $t^2$ calculations to search the corresponding
  $t$ tables of size $m × t$.


However, my result doesn't agree with his. Here is my idea:

If we count a single application of a reduction function as 0.5 calculation, we'll have to do $0.5 + 1.5 + ... + t-0.5$ calculations in the worst case when looking up in a rainbow chart, that is, $\frac{t^2}{2}$ calculations, greater than the author's $\frac{t(t-1)}{2}$. In contrast, the original method seems to call for $t(t-\frac{1}{2})$ calculations, fewer than the author's $t^2$.

Also, the author's $\frac{t(t-1)}{2}$ and $t^2$ gives $0$ and $1$ respectively when $t=1$, which seems strange.

So who is wrong?
If we count a single application of a reduction function as 0.5 calculation [...]


That does not seem to be an assumption made in the paper? I would expect the reduction function to take much less time than a hash/cipher, so discounting them completely is a good enough approximation. That gives the value in the paper.

If you count it as 0.5, then it would take $0.5 + 2 + 3.5 +\dots + (t-1+0.5t)$ rather than what you have, since at each step you add 1.5 work for both another hash/cipher and another reduction.


  In contrast, the original method seems to call for $t(t-\frac{1}{2})$ calculations, fewer than the author's $t^2$.


This part I am not sure about. I would think it should be $t(t-1)$, which matches the later text saying that a rainbow table approach takes half the time of the original.