つまりデータ量に比例した時間がかかるかと。
「新鮮な奴はレスポンス良く、古いのはまったり」という処理が有効になるのは、
たとえば焼きの人が「あなたはこういう理由で焼かれています」的な場面ですかね。
時間的局所性が高い状況下でなら効果はあると思います。
真紅さんの言うように3年前に焼かれたものよりは昨日今日焼かれたものの問い合わせのほうが（一般的には）多いでしょう。
ただ、一般的でない場面もあって、ISP新規ユーザや既存ユーザのIPアドレスが変わった（焼かれたIPを踏んだ）などの理由で書けなくなった場合ですね。
書けなくなったのは昨日今日かもしれないけど、焼かれたのは3年前かもしれないです。
この場合、最悪すべてを検索して見つかる（リスト末尾にある）こともありえます。
（状況的に不具合になりますが、データがない場合は最悪の探索時間になります。）
