educative.io

Is not StringBuilder.insert an expensive operation?

Courses
, ,
#1

In the example, a string is reversed by appending content to the beginning of a StringBuilder. Is not that operation a O(n) operation by itself? Would not it be better to use the reversed method in StringBuilder before the method returns?

I guess another alternative would be to transverse the string in reverse order to begin with so that we introduce the data in the StringBuilder in the right direction and we can save the reverse operation.

Moreover, if we are already using a StringBuilder that has a Stack like API, cannot we just use the StringBuilder as the only data structure?

1 Like
#2

Hello @luish,

Thank you for sharing this detailed analysis of the time complexity of this code. You’re correct to mention that the cost for appending characters to the beginning of the StringBuilder will cost O(n) time. Instead we can use the StringBuilder.reverse() before returning the result is a more efficient approach, turning it into an O(n) operation. Alternatively, traversing the string in reverse order and appending characters to the StringBuilder in the correct order also maintains O(n) complexity.

Furthermore, using StringBuilder alone as a stack-like structure is possible, but we must be careful with the complexity of operations like deleteCharAt. Alternatively, Stack performs the push and pop operations in constant time. Regardless of this, the StringBuilder only solution code can be used as an alternative approach to solving this problem.

Feel free to share more suggestions and feedback. We’d be happy to help. Thanks!

Happy learning!