Дольше считать разложение одного и того же числа на множители или разложение этого же числа в сумму чисел Фибоначчи?

Разложение на множители работает за O(sqrt(N)).
Насчет чисел фибоначчи, мне кажется за O((logn)^2). Если есть ряд этих чисел