Big O notation for Reverse String 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)?

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

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

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

    /// &lt;summary&gt;
    /// Time Complexity: o(n)
    /// Space Complexity: o(1)
    /// &lt;/summary&gt;
    /// &lt;param name="str"&gt;&lt;/param&gt;
    /// &lt;returns&gt;&lt;/returns&gt;
    public static string ReverseString_ForEachConcat(string str)
    {

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

    /// &lt;summary&gt;
    /// Time Complexity: o(n)
    /// Space Complexity: o(n)
    /// &lt;/summary&gt;
    /// &lt;param name="str"&gt;&lt;/param&gt;
    /// &lt;returns&gt;&lt;/returns&gt;
    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());
    }

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

    /// &lt;summary&gt;
    /// Time Complexity: o(n)
    /// Space Complexity: o(1)
    /// &lt;/summary&gt;
    /// &lt;param name="str"&gt;&lt;/param&gt;
    /// &lt;returns&gt;&lt;/returns&gt;
    public static string ReverseString_LINQ(string str)        
        =&gt; string.Join("", str.Reverse());
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.