2

Below Algorithm is for sum of all elements in an array.

function sumofnumbers(a[],n)
   {
     sum=0
     for(i=0 to n)
         sum=sum+a[i]
     print(sum)
   }

Can anyone help me out with this Algorithm analysis. why the space complexity of above algorithm is O(n)? According to me this must be O(1). Because we are not considering any extra space over here. We are using given space to calculate sum of elements in array. for example in some sorting technique to sort elements we take extra array.

According to me

Formula to calculate Space complexity:

 Space complexity = Input size + Auxillary space

Every algorithm contains it's required/own input size that is whatever space required by program to execute. So we have to consider only extra space(Auxillary space) required by program to execute that is other than Input size to calculate Space complexity.
So I applied this concept is it True??

And when to consider Both parameter(i.e Input size and Auxillary Space) to calculate Space complexity? because in some example like Linear Search i seen that some times they are not using Input size ?

Thank you!!

Sneha Mathadawar
  • 23
  • 6
  • 3
    Yes, looks like O(N) time and O(1) space to me. – Sergio Tulentsev Jun 07 '21 at 16:09
  • Space is O(N) because it needs to hold its input. Think in terms of a Turing Machine -- the program needs to scan the entire input which is written on the tape. – wcochran Jun 07 '21 at 16:12
  • 2
    @wcochran: that sounds like time complexity – Sergio Tulentsev Jun 07 '21 at 16:13
  • 2
    Who said it is linear-space? space-complexity is the complexity of the auxiliary ribbon of the turing-machine. Taking into account the size of the input would mean that you will never achieve sublinear space complexity, LOGSPACE for example. – Jean-Baptiste Yunès Jun 07 '21 at 16:15
  • 1
    @Jean-BaptisteYunès you are correct. Space complexity does not consider the input size as part of the memory needed to process the input ... https://stackoverflow.com/questions/43260889/what-is-o1-space-complexity#:~:text=In%20contrast%2C%20O(N),respect%20to%20the%20input%20size.&text=It%20is%20just%20the%20amount%20of%20memory%20used%20by%20a%20program.&text=Operations%20performed%20on%20this%20data,array%20of%20fixed%20size%20100. – wcochran Jun 07 '21 at 16:20

2 Answers2

2

I believe you are correct. The space complexity does not change with increasing values of N - hence O(1). Reference https://www.baeldung.com/cs/space-complexity

MrMxyzptlk20
  • 19
  • 3
1

If the input is large, the total sum can be large too, which results in non-constant space.

i.e. 112345 ^ 1235634 cannot fit in a constant 64-bit int. So, you need larger space to hold the sum (could be str, or list, or linked-list).

Iwan tandjaya
  • 11
  • 1