Что такое повторение, если базовый регистр равен O (n)?

Question

Мы должны создать алгоритм и найти и решить его повторение. Нахождение рецидива меня насторожило.

foo(A, C) 
    if (C.Length = 0) 
    Sum(A) 
    else 
    t = C.Pop() 
    A.Push(t) 
    foo(A,C) 
    foo(A,C) 

Первоначально A пуст и C.Length = n. Я не могу дать настоящий алгоритм, потому что это запрещено.

Мой инструктор сказал мне, что я могу попытаться использовать 2 переменные. Это то, что я придумал:

T(n, i) = { n    if i = 0 
      2*T(n, i-1) + C if i != 0 

Я не мог решить, поэтому я также пытался решить повторения только с одной переменной:

T(n) = { n0     if n = 0 
     2*T(n-1) + C  if n != 0 

Где п0 начальное значение п ,

Как формируется повторение из алгоритма, где сложность базового случая равна O (n)?

Answer 1

Пусть f (n) - сложность, если C имеет размер n. Пусть N - исходный размер C.

Тогда f (0) = N и f (n) = 2 * f (n - 1) + c.

Это решение имеет решение f (n) = N * 2^n + (2^n - 1) * c, и поэтому f (N) = O (N * 2^N).