Tractable Problems

Algorithms included: nth Fibonacci, Karatsuba Algorithm

1. nth Fibonacci

The Fibonacci numbers are the numbers in the following integer sequence - 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ......
Method 1: (Using Recursion)
We use a function int fib(int n) that returns Fn. For example, if n = 0, then fib() should return 0. If n = 1, then it should return 1. For n > 1, it should return Fn-1 + Fn-2. Time complexity is T(n) = T(n-1) + T(n-2) which is exponential. 


def Fibonacci(n):
# First Fibonacci number is 0
if n==0:
    return 0
# Second Fibonacci number is 1
elif n==1:
    return 1
else:
    return Fibonacci(n-1)+Fibonacci(n-2)


Method 2: (Using Iteration)
Normal iterative approach which completely removes the overlapping computation in the recursion. 


def Fibonacci(n):
# First Fibonacci number is 0
if n==0:
    return 0
f[0]=0
f[1]=1
for i in range(2,n):
    f[i]=f[i-1]+f[i-2]
return f[n]


Method 3: (Using Direct Formula)
Direct formula for the nth Fibonacci number which is Fn = {[(√5 + 1)/2] ^ n} / √5. Time complexity is O(log n) and space complexity is O(1). 


import math
def fibo(n):
    phi = (1 + math.sqrt(5)) / 2
    return round(pow(phi, n) / math.sqrt(5))



2. Karatsuba Algorithm

Karatsuba’s algorithm reduces the multiplication of two n-digit numbers to at most nlog23} ≈ n1.585 single-digit multiplications in general and exactly nlog23 when n is a power of 2. Although the familiar grade school algorithm for multiplying numbers is how we work through multiplication in our day-to-day lives, it’s slower O(n2) in comparison. Karatsuba observed that xy can be computed in only three multiplications, at the cost of a few extra additions. Using Divide and Conquer, we can multiply two integers in less time complexity. We divide the given numbers in two halves. 


def karatsuba(x,y):
"""Function to multiply 2 numbers in a more efficient manner than the grade school algorithm"""
if len(str(x)) == 1 or len(str(y)) == 1:
	return x*y
else:
	n = max(len(str(x)),len(str(y)))
	nby2 = n / 2
	
	a = x / 10**(nby2)
	b = x % 10**(nby2)
	c = y / 10**(nby2)
	d = y % 10**(nby2)
	
	ac = karatsuba(a,c)
	bd = karatsuba(b,d)
	ad_plus_bc = karatsuba(a+b,c+d) - ac - bd
    
    	# this little trick, writing n as 2*nby2 takes care of both even and odd n
	prod = ac * 10**(2*nby2) + (ad_plus_bc * 10**nby2) + bd
	return prod

Time complexity of the above solution is O(nlog23).

Problems Solved