Question

static int product(int x,int y){

if(x==0||y==0){//checking if x or y is 0

return 0;//if x or y is 0, then the return value and x*y will be zero.

}else if(y<0&&x<0){

x=-x;//Changing the sign of x

y=-y;//Changing the sign of y

}else if(x>=1){

return (y+product(x-1,y));

}

return (x+product(x,y-1));

}

find the space complexity and the time complexity of the above algorithm.

Answer 1

Time Complexity

Let the function T(x,y) denotes the number of operations perform by calling the product function:-

• Base Case - When either of x or y is 0 , the function returns 0.Hence , it takes a fixed number of operations say 1.
  
  T(0,y) or T(y,0) = 1
  
• Recursive Case:- If x or y is greater than 0, it will perform constant operations having constant cost say 1 and make a recursive call to T(x-1,y) if x>0 else T(x,y-1) .
  T(x,y) = 1+T(x-1,y) if x>0
  T(x,y) = 1+T(x,y-1) otherwise
  
  Case 1:- x>0
  T(x,y) = 1+T(x-1,y)
  1+T(x-1,y) = 2+ T(x-2,y)
  2+ T(x-2,y) = 3+ T(x-3,y)
  .
  .
  .
  .
  T(x,y) = k + T(x-k,y)
  if k = x
  T(x,y) = x+1                           {T(0,y) = 1}
  
  TIme Complexity = O(x)
  
  Case 2:- x<1
  Similarly , for this case
  
  Time Complexity = O(y)

---------------------------------------------------------------------------------

Space Complexity - The space complexity is determined by the depth of recursion tree i.e the number of return statements as every recursive call is stored in system stack.

• Case 1:-x>0
  For this case, the number of recursive calls are x+1
  Space Complexity = O(x)
  
• Case 2:-x<1
  For this case, the number of recursive calls are y+1
  Space Complexity = O(y)