оценка мемоизированного алгоритма.

Для рекурсивной реализации оценкой будет само число Каталана

ни..ера себе эффективность :) imho должно вычисляться как разница биномиальных коэф. и если память не изменяет - оценка по скорости O(n^2)

Ну на самом деле с мемоизацией оно работает очень быстро и вполне эффективно ;)

Но сам вопрос не в эффективности, а в том как оценить алгоритм с мемоизацией.

мне почему-то кажется что он тоже будет O(n^2)

А в чем вообще сомнение? Двойной цикл по N - вот и O(N^2). Стоит, правда, N сделаться хоть чуть-чуть большим - и игнорировать сложность операций умножения и сложения уже не выйдет.

> Ну на самом деле с мемоизацией оно работает очень быстро и вполне эффективно ;)
Если ищется одно число Каталана, то на самом деле вычисление одного биномиального коэффициента и деление его на N+1 выйдет вам в O(N), не так ли? Опять-таки, для небольших чисел. Хотя и для больших может оказаться лучше через биномиальные коэффициенты, так как они не потребуют быстрого умножения двух длинных чисел.