Big O notation for Reverse String
There are a couple of constructs in there that can be improved.


string.Join("", charArray), repeated a lot. string has a constructor that takes a char[], which is a lot faster. They are both linear time, which your question seems to focus on, but in terms of actual efficiency the difference is nearly two orders of magnitude in some tests (actual impact of course varies).
new Stack(), so.. the old stack, from the .NET 1.1 days? Don't use that one, use Stack&lt;T&gt;. Especially if the things you're putting in them are value types, which would have to be boxed in the old non-generic Stack.


For ReverseString_ForEachConcat, I don't agree that the time complexity is O(n). At every step, the old string is copied over into the new string, with something concatenated in front of it. So in the second iteration there is 1 copied character, in the third iteration there are 2 copied characters etc. That's a classic O(n²) pattern.

I think we could also argue about whether or not it takes constant space. The many old versions of the string can disappear quickly, but while the concatenation is happening, both the old string and the result of the concatenation need to exist. In the last iteration, that means that while the final result is being made (the size of which doesn't count), there is an other string in play of nearly the same size, so O(n) worth of auxiliary space.