Question

What is the auxiliary space and space complexity for a dynamic programming algorithm with time complexity of O(n^2)? Justify.

Answer 1

Auxiliary Space complexity of dynamic pragraming :-

• Auxilary space complexity of algoritham is the extra space or temporary space used by algoritham during its execution .
• Think temporary arrays , pointer etc.
• The temporary space is allocated in order to solve problem .
• For example :- merge sort uses new array to solve to solve problem so it has auxilary space complexity is O(n), where has Quick sort does not uses extra space so auxilary space is O(1).
• With respect to time complexity O( n^2 ) then Auxilary time complexity is O(n) .

• int count = 0;
  for (int i = N; i > 0; i /= 2) 
      for (int j = 0; j < i; j++) 
          count++;

  Because auxilary space require extra space .

Space Complexity of dynamic programing :-

• Space complexity is total space taken by algoritham with respect to input size .
• space complexity = Auxilary space complexity + space used by input value .
• with respect to time complexity O(n^2) the space complexity is O(n).

•  for(i = 0; i < n; i++)
    {
      for (j=i+1; j<=n;j++)
      {
      sum = arr[j] + arr[i];
       }
    }