Sum of Digits of an Integer Using Recursion

Write a Python program to get the sum of the digits of a non-negative integer using recursion.

Time and space complexity

Exercise 1

What is the time and space complexity of the following code:

a = 0
b = 0
for i in range(N):
  a = a + random()
 
for i in range(M):
  b= b + random()

Exercise 2

What is the time complexity of the following code:

a = 0;
for i in range(N):
  for j in reversed(range(i,N)):
    a = a + i + j;

Exercise 3

What is the time complexity of the following code:

k = 0;
for i in range(n//2,n):
  for j in range(2,n,pow(2,j)):
        k = k + n / 2;

Do the following exercises:

Then, compute the time complexity and space complexity of counting sort.