from timeMyPrograms import *


def fib(n):
 	if (n <= 1):
 		return n 
 	else:
 		return fib(n-1) + fib(n-2)


# Theorie sagt: O(n)
# Empirie sagt: O(n^2)

# Python unterstützt nativ BigIntegers


# Im i-ten Schleifendurchlauf braucht
# die Addition "c = a+b" 
# Theta(i) Schritte.
# 
# Also brauchen wir insgesamt
# 
# C(1 + 2 + 3 + ... + n)
# Schritte.
# = Theta(n^2)

def fibIt(n):
	a = 0 
	b = 1
	for i in range(n):
		c = a+b 
		# wenn a und b groß sind, 
		# dann geht a+b nicht mehr 
		# in O(1)
		# Sondern in Theta(Anzahl der Bytes)
		# Theta(Anzahl der  Bits)
		# Theta(log_2(a))
		# Theta(log_2(Fib(i)))
		# Theta(log_2(c^i))
		# Theta(i*log_2(c))
		# Theta(i)


		a = b 
		b = c 
	return a 

# Laufzeitanalyse. Wie lange braucht fibIt(n)? 


# Behauptung: die Laufzeit ist proportional zur Anzahl
# der Schleifendurchläufe. 
# In anderen Worten:
# Sie ist O(n). Sie ist linear.

# Linear heißt: doppelt so großer Input, 
# doppelt so große Laufzeit
#




# n 		Laufzeit
# 100000	0.127
# 200000	0.48 [proportional waere 2*0.127]
# 400000	1.87
# 800000	7.5


# Untere Schranken: 
# Um F_n zu berechnen müssen Sie ja 
# zumindest mal alle Stellen des Ergebnisses
# F_n hinschreiben.
#
# Sie brauchen also mindesntens
# Theta(log_2(F_n)) = Theta(n) Schritte,
# weil das Ausdrucken bereits so lange dauert.