Gamja's Farm

import numpy as np
def Fibonacci_1(number):#O(2^n)
    if(number == 0):
        return 0
    elif(number == 1):
        return 1
    return Fibonacci_1(number-1) + Fibonacci_1(number-2)

def Fibonacci_2(M, number):#O(logn)
     if(number > 1):
         if number % 2 ==0:
             M = Fibonacci_2(M, number/2)
             M = np.dot(M,M)
         elif number % 2 ==1:
             M = Fibonacci_2(M,(number-1)/2)
             M = np.dot(M,M)
             M_1 = np.array([[1,1],[1,0]])             
             M = np.dot(M,M_1)
     return M

def Fibonacci_3(number):
    Fibonacci_T = []
    if number ==0 or number == 1:
        return number
    Fibonacci_T.append(0)
    Fibonacci_T.append(1)
    for i in range(2,number+1):
        Fibonacci_T.append(Fibonacci_T[i-1]+Fibonacci_T[i-2])
    result = Fibonacci_T
    return result

if __name__=='__main__':
    M=np.array([[1,1],[1,0]])
    a = (Fibonacci_2(M,10))
    F2 = a[0][1]
    b = Fibonacci_3(10)
    F3 = b[len(b)-1]
    
    
    print("O(2^n)")
    print(Fibonacci_1(10))
    print("O(log n)")
    print(F2)
    print("O(n)")
    print(F3)

def Power(Base, Exponent):
    result = Base
    count = 1
    ex_Exponent = Exponent
    list1 = []
    while(ex_Exponent > 1):
        if ex_Exponent % 2 == 0:
            list1.append(0)
            ex_Exponent = ex_Exponent/2
        else:
            list1.append(1)
            ex_Exponent = (ex_Exponent - 1)/2
    list1_len = len(list1)
    for count in range(list1_len):
        if list1[list1_len - count -1] == 0:
            result = result * result
        else:
            result = result * result * Base
    return result

if __name__=='__main__':
    print(Power(11,3))