Асимптотическое время выполнения функции списка к дереву

У меня есть a merge функция, которая занимает время O(log n) объединить два дерева в одно и a listToTree функция, которая преобразовывает первоначальный список элементов к одноэлементным деревьям и неоднократно звонит merge на каждой последовательной паре деревьев, пока не остается только одно дерево.

Функциональные подписи и соответствующие реализации следующие:

merge :: Tree a -> Tree a -> Tree a --// O(log n) where n is size of input trees
singleton :: a -> Tree a            --// O(1)
empty :: Tree a                     --// O(1)
listToTree :: [a] -> Tree a         --// Supposedly O(n)

listToTree = listToTreeR . (map singleton)

listToTreeR :: [Tree a] -> Tree a
listToTreeR []     = empty
listToTreeR (x:[]) = x
listToTreeR xs     = listToTreeR (mergePairs xs)

mergePairs :: [Tree a] -> [Tree a]
mergePairs []       = []
mergePairs (x:[])   = [x]
mergePairs (x:y:xs) = merge x y : mergePairs xs

Это - немного упрощенная версия упражнения 3.3 в Чисто Функциональных Структурах данных Chris Okasaki.

Согласно осуществлению, я теперь покажу это listToTree берет O(n) время. Который я не могу.:-(

Существуют тривиально ceil(log n) рекурсивные вызовы listToTreeR, значение ceil(log n) вызовы к mergePairs.

Время выполнения mergePairs зависит от длины списка и размеров деревьев. Длина списка 2^h-1, и размеры деревьев log(n/(2^h)), где h=log n первый рекурсивный шаг, и h=1 последний рекурсивный шаг. Каждый вызов к mergePairs таким образом занимает время (2^h-1) * log(n/(2^h))

Я испытываю затруднения при взятии этого анализа дальше. Кто-либо может дать мне подсказку в правильном направлении?