What is the complexity of the below code with respect to memory ?

Question

Hi, I read about Big-O Notation from here and had few questions on calculating the complexity.So for the below code i have calculated the complexity. need your inputs for the same.

    private void reverse(String strToRevers) 
    {
        if(strToRevers.length() == 0)
        {
            return ;
        }
        else 
        {
            reverse(strToRevers.substring(1));
            System.out.print(strToRevers.charAt(0));
        }
    }

If the memory factor is considered then the complexity of above code for a string of n characters is O(n^2). The explanation is for a string that consists of n characters, the below function would be called recursively n-1 times and each function call creates a string of single character(stringToReverse.charAT(0)). Hence it is n*(n-1)*2 which translates to o(n^2). Let me know if this is right ?

Answer 1

Hence it is n*(n-1)*2 which translates to o(n^2). Let me know if this is right ?

Almost: it's n * (n-1) / 2, not *2, which is also O(n^2). Note that o(n^2) (little-O) means something else, so the distinction is important.

This is assuming we're considering this as pseudocode. Language-specific implementations and smart compilers may be able to improve the running time substantially. For instance, a compiler that can observe that you're simply reversing the string might just do an in-place reverse, which is O(n).

Answer 2

Looks like Java, so it's not O(n**2). That's because strings share the underlying character sequence buffers; they can do this because they are immutable objects.

But it is O(n) in stack space. That's not good. It's better to allocate a mutable working buffer of characters, reverse the string into that, and then print the whole lot at once.