Order of Growth of Recursive Function

Question

Следующий вопрос, который задавали в GRE computer science test 2001.

Q-67: Рассмотрите следующие C код.

int f(int x) { 
    if(x<1) { 
     return 1; 
    } else { 
     return f(x-1)+g(x); 
    } 
} 

int g(int x) { 
    if(x<2) { 
     return 1; 
    } else { 
     return f(x-1)+g(x/2); 
    } 
} 

из следующих действий, который наилучшим образом описывает рост из F (х) как функция х?

(А) Логарифмические (Б) Линейный (С) Квадратичные (D) Кубический (Е) Экспоненциальное

Кстати, правильный ответ(E) Экспоненциальный (упомянутый в его ответе ключ). Но я не знаю точного метода решения этого.

Может ли кто-нибудь решить эту проблему Повторные отношения? Есть ли у вас альтернативный подход?

Пожалуйста, поделитесь своими взглядами.

Answer 1

Я думаю, что это может быть упрощена f(x) >= f(x-1)+f(x-1) for x>1, потому g(x) = f(x-1)+g(x/2) >= f(x-1) for x>1. Первое неравенство - это только f(x) >= 2*f(x-1), и отсюда легко получить, что f(x) >= 2^x*f(1) (значение f по крайней мере удваивается каждый раз, когда x растет на 1).