0

This might sound dumb but I was wondering while thinking a bit, can't you play around with an algorithm and make O(n) memory seem O(1)?

(Java) Let's say you have an array of N elements of true or false. Then that array would result in O(n) memory.

However, if we have an array of say, "FFFFFTFTFFT" with each charAt(i) answering the result of the i-th index of the array, haven't we used only O(1) memory or is it considered O(n) memory since String is size of O(n) itself?

Let's take this further. If we have an N-array of true and false and convert this to bytes, we use even less memory. Then is the byte also considered O(1) memory or O(n) memory? For instance, let's say n = 6. Then array size is 6 = O(n). But the byte size is just 1 byte since 1 byte can store 8 different values (8 bits). So is this O(1) or is this O(n) since for large N we get the following case...: N equals 10000. Array is O(n) memory but is a byte what memory? Cause our byte is O(n/8) = O(n)?

Nicholas K
  • 15,148
  • 7
  • 31
  • 57
AccCreate
  • 373
  • 3
  • 6
  • A string and a `char[]` aren't that different. If you have an array of true and false, you have a bit-vector, not a `byte[]`, but you still have N elements – OneCricketeer Sep 20 '18 at 03:26
  • 1
    Yes, you have to include the size of the (underlying) array. – chrylis -cautiouslyoptimistic- Sep 20 '18 at 03:31
  • A byte cannot "store 8 different values". It can store 8 values selected from a set of two possible values (from the set {0, 1}). Alternatively, it can store 1 value selected from a set of 2^8 = 256 possible values. Or any variation between (such as 4 values selected from a set of 2^2 possible values). – Ted Hopp Sep 20 '18 at 04:07
  • Duplicate of [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) – Bernhard Barker Sep 20 '18 at 08:18
  • `O(n/8) = O(n)` - didn't you just answer your own question here? As in: it will be O(n) no matter how many bits each element takes up, as long as it's a constant amount. – Bernhard Barker Sep 20 '18 at 08:20

3 Answers3

2

All the cases you've described are O(n), it describes the limiting behavior when n tends towards infinity, saying mathematically:

f(n) = O(n), as n -> INF equals to f(n)/n -> const, as n -> INF, where const <> 0

So 10*n + 100 = O(n) and 0.1*n = O(n).

And as you wrote next statement is correct too: O(n/8) = O(n) = O(n/const)

marme1ad
  • 1,253
  • 8
  • 8
0

I'm not sure you understand the concepts of Big O completely, but you still have N elements in each of the listed cases.

The notation O(N) is an upper bound for a function of N elements, not so much defined by the size of the underlying datatypes, since as noted O(N/8) = O(N).

So, example,

If we have an N-array of true and false and convert this to bytes

You are converting N elements into N bytes. This is O(N) time complexity. You stored 2 * O(N) total arrays, resulting in O(N) space complexity.

charAt(i)

This operation alone is O(1) time complexity because you are accessing one element. But you have N elements in an array or string, so it is O(N) space complexity

I'm not really sure there is a common O(1) space complexity algorithm (outside of simple math operations)

OneCricketeer
  • 179,855
  • 19
  • 132
  • 245
  • 1
    As soon as the memory is bounded (independent of the input size), you have O(1) space complexity. This does not restrict you to "a single memory register". – Henry Sep 20 '18 at 03:52
0

There is another misconception here: in order to truly make a "character container" with that O(1) property (respectively: O(log n), as the required memory still grows with growing data), that would only work for exactly that: strings that contain n characters of one kind, and 1 character of another kind.

In such cases, yes, you would only need to remember the index that has the different character. That is similar to defining a super sparse matrix: if only one value is != 0 in a huge matrix, you could store only the corresponding indexes instead of the whole matrix with gazillions of 0 values.

And of course: there are libraries that do such things for sparse matrixes to reduce the cost of keeping known 0 values in memory. Why remember something when you can (easily) compute it?!

GhostCat
  • 137,827
  • 25
  • 176
  • 248
  • Strictly speaking, the string example would have O(log n) space complexity because the larger n, the larger the number needs to be. – Henry Sep 20 '18 at 04:00