Hi I'm a CS student and I'm trying to get a better understanding of Big O notation and was hoping somebody could explain this to me.

char[] arr = new char[str.length()];

Does this have complexity O(1) or O(n)? In my full program this snippet is inside a method, with String str being passed to it. I do not understand if it is O(n) because the size of the array varies with the length of the string, or O(1) because the string length has already been declared outside of the method. Please help me.

Okay sorry I should have specified this and saw a comment point it out. I'm asking about space complexity, since I do not fully understand the logic behind it.

CodePudding user response：

Complexities are variable based. We tend to shortcut it, someone might say: "This algorithm is O(n)". But this is an oversimplified statement. After all, what in the blazes is n here? Somebody needs to define it.

new char[str.length()] has time complexity of O(n) (n = size of the input string), but that's only because in java specifically, any declared array is guaranteed to be zeroed out for you. str.length() doesn't iterate through the entire string, it just returns a value from a field. In languages like C where an allocation is filled with random garbage, it'd have been O(1).

The space complexity is linear to the length of the input string - in other words, you have to say, to be complete:

• Let us define n as: The length of the str variable.
• Then the space complexity of new char[str.length()] is O(n).

After all, if you double the size of the input string, you double the size of the memory that new char[str.length()] needs.

That's what O(x) is about: Make a chart; the X axis is the size of your input, the Y axis is the space requirements, or time taken, of an algorithm. Now go run the algorithm with size=1, then with size=2, and keep drawing in the points (at size=18, the algorithm takes 89 bytes. Okay, so draw that in: Draw a point at X=18,Y=89).

Then draw the 'fitting line' through all those points. It'll be a random mess at first, but look to the right far enough and eventually it'll stabilize into a recognizable shape. When does it stabilize? Who knows, that is not what big-O notation is about. That involves properties like CPU cache page sizes and which music is currently playing on your music player.

But eventually, it will. Once it does, what does it look like? O(x^2) means: Looks like the y=x^2 curve.

Hence, O(n) means: Double the input, then also the output doubles.

That whole 'remember to define n first!' thing comes up the moemnt your algorithm introduces more variables. Imagine this method:

/**
 * Returns a string consisting of {@code in}, repeated {@code n} times.
 * For example, {@code replicate("hello", 3)} returns {@code "hellohellohello"}
 */
public void replicate(String in, int n) {
  StringBuilder out = new StringBuilder(in.length() * n);
  for (int i = 0; i < n; i  ) out.append(in);
  return out.toString();
}

this algorithm's time complexity is more or less O(n m) where we define n as, well, n, and m as the length of in. If, of course, in in your case is irrelevant, then that boils down to a constant and you can just treat this algorithm as O(n) - there's no way to tell unless you provide the context of which variables you actually care to analyse.

The point of big-O notation is to explain how the algorithm behaves if you change the 'size' of the inputs. Naturally then if there's a property you don't care about as an input or one you hold constant then trivially that ceases to be relevant to the analysis.

[1] It's complicated; attempting to allocate a particularly large block will cause some garbage collection, which takes time, and that time is linear relative to how much you need, but usually memory allocations are free (or rather, O(1) - independent of how much you need) because there's enough heap for it. This shows primarily how O(n) is an academic concept that doesn't quite survive contact with real life.

CodePudding user response：

The time complexity of the above piece of code is O(1) as we are just accessing a constant. The size of the string is calculated during string modification operations.

Now the space complexity is O(n) as you are creating a new character array of the size of the string.