Две цитаты..

"Математик во мне говорит, что нет лучшего способа проверить, чем провести расчет. Итак, Алгоритм маляра Шлемиэля:

Маляр Шлемиэль подрядился красить пунктирные осевые линии на дорогах. В первый день он получил банку краски, поставил её на дорогу, и к концу дня покрасил 300 метров осевой линии. "Отлично!" сказал прораб, "быстро работаешь!" -- и заплатил ему копейку.

На следующий день Шлемиэль покрасил 150 метров. "Мда, это, конечно, не так здорово, как вчера, но приемлемо." -- сказал прораб и заплатил ему копейку.

На следующий день Шлемиэль покрасил 30 метров. "Всего лишь 30!" заорал прораб. "Это никуда не годится! В первый день было в десять раз больше! В чём дело?"

"Ничего не могу поделать," -- говорит Шлемиэль. "Каждый день я ухожу всё дальше и дальше от банки!"

Предположим, что кол-во закрашиваемых метров за один подход к банке одинаково и равно Dp, тогда в первый день маляр покрыл растояние:

Dp + Dp + 2Dp + 2Dp + 3Dp + 3Dp +... + M*Dp + M*Dp = [где M*Dp = 300] = 2Dp (1+2+3+... +M) .

Проще показать, если принять Dp=1 м, чтобы не писать громоздких формул, тогда

2(1+2+3+...+300) - это первый день

второй день:

(301 + 301 + 302 + 302 + ... + (N-1) + (N-1) + N + N = 2 (301 + 302 + (N-1) + N) = [ т.к. сумма натуряльного ряда 1+2 + 3+ N = N(N+1)/2 - так называемое треугольное число ] =

2* (N(N+1)/2 - 150*301) = N^2 + N - 90300 , А это O(N^2). Это если считать скорость нанесения разметки и скорость движения постоянными величинами. При этом, если отталкиваться от закрашенного расстояния, то время будет также O(N^2). Кстати, цифры приведенные Джоелом Спольски в данной ситуации довольно сильно преувеличены не в пользу маляра, чтобы это выяснить, достаточно решить квадратное уравнение. Как-то так..."

"Да.... Завидую людям, которые знают что такое “сумма натурального ряда“ и которые умеют определять сложность алгоритмов... Мне уже этого не познать, видимо"

Я лично отношусь к последней категории людей...