Объясните, пожалуйста, почему
def f(N):
if(N <= 1):
return 1
else:
x = f(N-1)
y = f(N-2)
return x+y
имеет O(2^n)
def f(N):
if(N <= 0):
return 2
if(N <= 5):
return f(N-1) * f(N-1)
else:
return f(5)*f(4)
имеет O(1)
В первом случае, при достаточно большом N на каждом шаге будет создаваться две ветви рекурсии, каждая из которых, в свою очередь, создаст ещё две ветви, те ещё и так далее, поэтому количество вызовов функции можно оценить как O(2^N).
Во втором случае, для любого N будет вызваны f(5) и f(4), каждая из этих ветвей выполниться за определённое количество операций, всего вызовов будет 1 + 2 + 4 + 8 + 16 + 32 = 61 для f(5) и 1 + 2 + 4 + 8 + 16 = 31 для f(4), это константа, поэтому асимптотика O(1).