If strings are immutable in .NET, then why does Substring take O(n) time?

Java used to reference larger strings, but:

Java changed its behavior to copying as well, to avoid leaking memory.

I feel like it can be improved though: why not just do the copying conditionally?

If the substring is at least half the size of the parent, one can reference the parent. Otherwise one can just make a copy. This avoids leaking a lot of memory while still providing a significant benefit.

None of the answers here addressed "the bracketing problem", which is to say that strings in .NET are represented as a combination of a BStr (the length stored in memory "before" the pointer) and a CStr (the string ends in a '\0').

The string "Hello there" is thus represented as

0B 00 00 00 48 00 65 00 6C 00 6F 00 20 00 74 00 68 00 65 00 72 00 65 00 00 00

(if assigned to a char* in a fixed-statement the pointer would point to the 0x48.)

This structure allows for fast lookup of the length of a string (useful in many contexts) and allows for the pointer to be passed in a P/Invoke to Win32 (or other) APIs which expect a null-terminated string.

When you do Substring(0, 5) the "oh, but I promised there'd be a null-character after the last character" rule says you need to make a copy. Even if you got the substring at the end then there'd be no place to put the length without corrupting the other variables.

Sometimes, though, you really do want to talk about "the middle of the string", and you don't necessarily care about the P/Invoke behavior. The recently added ReadOnlySpan<T> structure can be used to get a no-copy substring:

string s = "Hello there";
ReadOnlySpan<char> hello = s.AsSpan(0, 5);
ReadOnlySpan<char> ell = hello.Slice(1, 3);

The ReadOnlySpan<char> "substring" stores the length independently, and it does not guarantee that there's a '\0' after the end of the value. It can be used in many ways "like a string", but it is not "a string" since it doesn't have either BStr or CStr characteristics (much less both of them). If you never (directly) P/Invoke then there's not much of a difference (unless the API you want to call doesn't have a ReadOnlySpan<char> overload).

ReadOnlySpan<char> cannot be used as the field of a reference type, so there's also ReadOnlyMemory<char> (s.AsMemory(0, 5)), which is an indirect way of having a ReadOnlySpan<char>, so the same differences-from-string exist.

Some of the answers/comments on previous answers talked about it being wasteful to have the garbage collector have to keep a million-character string around while you continue to talk about 5 characters. That is precisely the behavior you can get with the ReadOnlySpan<char> approach. If you're just doing short computations, the ReadOnlySpan approach is probably better. If you need to persist it for a while and you're going to keep only a small percentage of the original string, doing a proper substring (to trim off the excess data) is probably better. There's a transition point somewhere in the middle, but it depends on your specific usage.