Доказательство экспоненциального времени выполнения по индукции

Question

У меня есть проблема, показывающая с индукцией, что данная функция

foo :: [Int] -> Int
foo    []  = 0
foo (x:xs) = max (max x (foo xs)) (max (-x) (foo xs))

, которое возвращает максимальное абсолютное значение заданного списка Int, имеет время выполнения O(2^n).

Я до сих пор так далеко:

t(0) = 1 и t(n>1)= 2 * t(n-1) + 4, где t показывает сумму вызовов foo и max для списка n элементов.

Base Case:            n = 0 => t(0) = 1 <= c * 2^0, for c >= 1
Induction Hypothesis: t(n) <= c * 2^n
Induction Step:       n -> n+1
                   => t(n+1) <= c * 2^{n+1}
                  <=> 2 * t(n) + 4 <= c * 2^{n+1} | Induction Hypothesis
                  <=> 2 * c * 2^n + 4 <= c * 2^{n+1}
                  <=> c * 2^{n+1} + 4 <= c * 2^{n+1}

что явно не так, и я не знаю, как решить эту проблему.

Заранее спасибо!

Answer 1

Давайте докажем немного более общее утверждение. Если сложность алгоритма такова:

 t(0) = c
 t(n) = a*t(n-1) + b 

при условии a>1 сложность алгоритма O(a^n).

Давайте выберем k1 = c, d = b/(a-1) (этот выбор d станет понятным в конце) и k2 = a + d. Давайте предположим, что a > c (в противном случае это были бы k1 = min(a,c), d= b/(max(a,c)-1) и k2 = max(a,c) + d, но мне лень писать все эти max и min). Мы хотим доказать, что

k1*a^n <= t(n) <= k2*a^n

но вот поворот, давайте докажем немного более строгую верхнюю границу:

k1*a^n <= t(n) <= k2*a^n - d

Базовый корпус :

c <= c <= (a + d) - d

очевидно верно

Шаг индукции :

Мы знаем, что

k1*a^n <= t(n) <= k2*a^n - d

верно и хочет доказать, что

k1*a^(n+1) <= t(n+1) <= k2*a^(n+1) - d

С левой стороны легко:

t(n+1) = a*t(n) + b >= a*t(n) >= a*(k1*a^n) = k1*a^(n+1)

Правая сторона немного сложнее

t(n+1) = a*t(n) + b <= a*(k2*a^n - d) + b = a*k2*a^n - a*b/(a-1) + b = k2*a^(n+1) - b/(a-1) =  k2*a^(n+1) - d

Последний шаг верен, потому что

a*b/(a-1) - b = b*(a/(a-1) - 1) = b*(a - (a-1))/(a-1) = b/(a-1)

другими словами

a*d - b = d

Answer 2

Давайте попробуем доказать более жесткий предел, как

t(n) <= c*2^n - k        (*)

для некоторых констант c и k.

Предполагая (*) по предположению индукции, получаем

t(n+1) 
= { recursive definition }
2*t(n) + 4
<= { induction hypothesis }
2*(c*2^n - k) + 4
<= { math }
c*2^(n+1) - 2k + 4
<= { ???? }
c*2^(n+1) - k

Теперь нам нужно только выбрать k, чтобы мы могли на самом деле оправдать последний шаг, но это легко.

Обратите внимание, что нам также необходимо проверить базовый случай t(0) и выбрать c.

Остальное я оставлю вам.