Big O notation for Reverse String

Question

I have here some methods which reverse string characters. Example if given string is "HELLO", it will returns "OLLEH". Are my big o notation for these approaches correct? And which approach is the most efficient (both time and space complexity)?

 /// <summary>
    /// Time Complexity: o(n)
    /// Space Complexity: o(n)
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public static string ReverseString_TwoArrays(string str)
    {
        char[] arr2 = new char[str.Length];

        for (int i = 0; i < str.Length; i++)
        {
            arr2[i] = str[str.Length - 1 - i];
        }
        return string.Join("",arr2);
    }

    /// <summary>
    /// Time Complexity: o(n)
    /// Space Complexity: o(1)
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public static string ReverseString_ClassicForLoop_ArrayIndex(string str)
    {
        StringBuilder sb = new StringBuilder();
        for (int i = str.Length - 1; i >= 0; i--)
        {
            sb.Append(str[i]);
        }
        return sb.ToString();
    }

    /// <summary>
    /// Time Complexity: o(n)
    /// Space Complexity: o(1)
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public static string ReverseString_ForEachConcat(string str)
    {

        string newStr = "";
        foreach (var item in str)
        {
            newStr = item.ToString() + newStr;
        }
        return newStr;
    }

    /// <summary>
    /// Time Complexity: o(n)
    /// Space Complexity: o(n)
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public static string ReverseString_Stack(string str)
    {
        var stack = new Stack();
        foreach (var item in str) // Time Complexity: o(n)
        {
            stack.Push(item); // Time Complexity: o(1)
        }
        return string.Join("", stack.ToArray());
    }

    /// <summary>
    /// Time Complexity: o(n)
    /// Space Complexity: o(n)
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public static string ReverseString_ArrayReverse(string str)
    {
        char[] arrChar = str.ToCharArray();            
        Array.Reverse(arrChar);
        return string.Join("", arrChar);
    }

    /// <summary>
    /// Time Complexity: o(n)
    /// Space Complexity: o(1)
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public static string ReverseString_LINQ(string str)        
        => string.Join("", str.Reverse());

Answer 1

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<T>. 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.

Answer 2

I was going to write this as a comment, but I have too much to talk about. When I first read the question, what was screaming at me is "WHY?!" Why go through such gymnastics? Are you intentionally trying to reinvent-the-wheel? If you are, then please tag the question with that tag.

If you are wanting to learn C#, and equally important, .NET, then I would suggest your focus should be on relying upon the framework.

For a simple Americanized string, where each character in the string is its own entity, you could try something like:

public static string ReverseString(string str)
{
    char[] arr2 = str.ToCharArray();
    Array.Reverse(arr2);
    return new string(arr2);
}

There are also examples here on CR where the reversing is done by only going halfway through the char array. The endpoints are swapped, and then indices are moved inward.

Note the above only works for some strings. If your input string contains certain characters from different cultures, these characters are known as surrogate pairs. You may loosely think of the pair as a composite. For such things, you do not want to reverse the individual characters because it breaks the surrogate relationship. Instead, you would use .NET and look into the StringInfo class (part of System.Globalization). The link provided shows how to honor surrogates.