Мы как то уже спорили на эту тему год или 2 назад, но ни к чему не пришли. Я остался при своем мнении ( хотя и услышал интересные вещи от вас и Ярослава ). Мое понимание , что оптимизаторы баз данных , когда считают стоимость не считают в терминах O(N). И это не спроста. дело в том ,что это слишком грубый подсчет , который подразумевает , что N стремится к бесконечности и никак не учитывается других фактов. Оптимизатор в оракле , например , высчитывает стоимость , как количество одноблочных чтений. И это более практично . вот в примере с индексами. Всем нам известен случай , что если вставка в индекс будет приводить к необходимости чтения с диска старых блоков то эта одна производительность , а если не будет ,то это другая . И это все O(logN). То есть считать практичнее в чтениях с диска в штуках и сравнивать их . Это даёт оценку более приближенную к времени выполнения ,чем Big O от количества строк