# 1 
def fun2(n, LIMIT):
	if n <= 0:
		return 
	if n < LIMIT:
		print(n)
		fun2(2*n, LIMIT)
		print(n)
#sol 1: 
# t(n) = c + t(2*n) = c + [c + t(4*n)] ... = kc + t(2^k n)
# the algorithm would stop when the parameter n >= LIMIT, that is n*2^k >= LIMIT
# which results in relation k >= log LIMIT - log n when the algorithm stops.

# 2
def fun1(n):
	i = 0
	if n > 1:
		print(n *'*')
		fun1(n-1)

	printString = ''
	for i in range(n):
		printString += '*'
	print(printString)

#sol 2: 
# t(n) = t(n-1) + n + n + C = t(n-1) + 2n + C
# t(n) = [t(n-2) + 2(n-2) + C] + 2n + C = t(n-3) + 3*2*n - 4 + n*C...
# ...  = t(1) + [sum_0,(n-1) 2n] + nC ---> O(n^2)

# 3
def reverseString(s):
	if len(s) == 0:
		return s
	return reverseString(s[1:]) + s[0]

#sol 3:
# t(n) = t(n-1) + C ... = t(1) + n*C ---> O(n)

# 4
def mysteryFunction(n):
	y = 0
	for i in range(n):
		for j in range(n):
			x = i**2
			y += x + j
	return y

# sol 4:
# O(n^2)

# 5
def mysteryFunction2(n):
	if n == 0:
		return
	else:
		x = 100
		while x > 0:
			x = x //2
		mysteryFunction(n-1)

# sol 5:
# t(n) = C + t(n-1) ... = n*C ---> O(n)


# 6
def foo(n):
	if n <= 1:
		return
	else:
		for i in range(n):
			x = i
		foo(n//2)
# sol 6:
# t(n) = t(n/2) + n = [t(n/4) + n/2] + n ... = t(n/2^k) + [sum_0,n n/2^k]
# ... = log n + 1 ---> O(log n)

# 7:
def fib(n):
	if n == 0:
		return 0
	elif n == 1:
		return 1
	else:
		return fib(n-1) + fib(n-2)

# sol 7:
# t(n) = C + t(n-1) + t(n-2) ---> O(2^n)

# 8 
def binary_search(the_array, the_key, imin, imax):
	if (imax < imin):
		return None
	else:
		imid = imin + ((imax - imin) // 2)
		if the_array[imid] > the_key:
			return binary_search(the_array, the_key, imin, imid-1)
		elif the_array[imid] < the_key:
			return binary_search(the_array, the_key, imid+1, imax)
		else:
			return imid

# sol 8:
# similar to #6, O(log n)

# 9 
# Towers of hanoi
def tower_of_hanoi(n , from_rod, to_rod, aux_rod): 
        if n == 1: 
                print( "Move disk 1 from rod",from_rod,"to rod",to_rod )
                return
        tower_of_hanoi(n-1, from_rod, aux_rod, to_rod) 
        print( "Move disk",n,"from rod",from_rod,"to rod",to_rod )
        tower_of_hanoi(n-1, aux_rod, to_rod, from_rod) 

# sol 9:
# similar to #7, O(2^n)


# 10 -> Very tricky
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def countAllNodes(node):
    if node is None:
        return 0
    return 1 + countAllNodes(node.left) + countAllNodes(node.right)

# sol 10:
# t(n) = t(n/2) + t(n/2) + C = 2*[t(n/2)] + C
# = 2*[t(n/4) + t(n/4) + C] + C = 2*2[t(n/4)] + (2+1)*C
# ... = 2^k * t(n/2^k) + (2^k + 2^(k-1) + ... +1)*C =
#log n * t(1) + n*C ---> O(n) using the fact sum_0,m 2^k = 2^m where m = log n