1

enter image description here

This is the code given in my algorithms book.We need to calculate its space complexity.

this is the answer given-

enter image description here

The space complexity is S=C+Sp and in this case Sp is zero as the code is independent of n. But I wanted to calculate the C part of the code and in this case it would be 5*2bytes=10 bytes considering a,x,n,0 and -1.

So my question is what would be the C in case a was a 2d matrix,do we consider it as 2 bytes only as in the case of 1d array or we take it as 4 bytes?

Enea Dume
  • 3,014
  • 3
  • 21
  • 36
ubuntu_noob
  • 2,305
  • 6
  • 23
  • 64
  • 0 is a somewhat uncommon answer, I would have said O(1). – Henry Aug 28 '18 at 11:58
  • This is not asymptotic notation – ubuntu_noob Aug 28 '18 at 11:59
  • 1
    Firstly, it is in asymptotic notation (The legendary Big-O). Secondly, I don't think you have to use 4 bytes, since that'll only change if you switch to a 64-bit system from a 32-bit one. – Nitin Pawar Aug 28 '18 at 12:13
  • @NitinPawar do we use the space required for 2-d array to be double that of 1 d array or the same? – ubuntu_noob Aug 28 '18 at 12:15
  • That is uncertain. It will be double only in the case of n x 2 matrix. It can expand further, depending on the other dimension of your matrix. – Nitin Pawar Aug 28 '18 at 12:18
  • 1
    It doesn't matter. Constant factors are irrelevant in asymptotic complexity - 1 bit and 1 TB would give you the same answer. – Bernhard Barker Aug 28 '18 at 13:13
  • [What is a plain English explanation of “Big O” notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) [Why is constant always dropped from big O analysis?](https://stackoverflow.com/questions/22188851/why-is-constant-always-dropped-from-big-o-analysis) – Bernhard Barker Aug 28 '18 at 13:19
  • @Dukeling: as the OP already said, he is not after asymptotic complexities but exact complexities. (Whether this makes sense or not in the O(1) case is another matter.) –  Aug 28 '18 at 14:03
  • @YvesDaoust I'm not familiar with the concept of "exact complexities". If this is about "the exact amount of space used", that will come down to the specific programming language, operating system and system architecture used (among other factors). – Bernhard Barker Aug 28 '18 at 14:43
  • @Dukeling: this is obviously C++ and it might be that the book refers to the old 16 bits architecture. The OS has little to do here. –  Aug 28 '18 at 14:57

1 Answers1

0

Pointers and integers are no more 16 bits since the mid-eighties so I wonder what you mean with your 2 bytes.

Also note that your accounting of space is a little weird. You don't count the variable i, but you do count literal constants, which usually appear as immediate arguments in the assembly code.

Anyway, on a 32 bits machine, all addresses (and pointers) are represented on 4 bytes and the extra accounting of array dimensions is performed by the compiler and hard-coded into the assembly.

On a 64 bits machine, count 8 bytes per pointer and 4 bytes per int.