7

A program I'm working on converts an array of integers to a string using string builder. I'm trying to determine the time complexity of this approach.

user253122
  • 119
  • 1
  • 1
  • 7
  • 1
    What exactly do you mean by "efficiency"? What is the criterion you are trying to optimize for? – Andy Turner Apr 15 '17 at 14:44
  • 2
    It's also worth pointing out that you need to define efficiency of one approach as being with respect to another feasible approach. As in, it takes vast amounts of fuel to launch a satellite into orbit, [it's not very efficient](https://space.stackexchange.com/a/17925) (as in power usefully expended); but in the absence of an alternative, the "inefficient" approach is all you can do, so the inefficiency is largely irrelevant. So, what is your alternative to string builder? – Andy Turner Apr 15 '17 at 14:51

2 Answers2

2

Check out: https://stackoverflow.com/a/7156703/7294647

Basically, it's not clear what the time complexity is for StringBuilder#append as it depends on its implementation, so you shouldn't have to worry about it.

There might be a more efficient way of approaching your int[]-String conversion depending on what you're actually trying to achieve.

Community
  • 1
  • 1
Jacob G.
  • 28,856
  • 5
  • 62
  • 116
2

If the StringBuilder needs to increase its capacity, that involves copying the entire character array to a new array. You can avoid this by initially setting the capacity so it won't have to do this. (This should be easy since you know the length of the int array and the maximum number of characters in the String representation of an int.)

If you avoid the need to increase the capacity, the complexity would seem to just be O(n). When you append, you're just copying the character array from the String to the end of the character array in the StringBuilder.

(Yes, it depends on the implementation, but it would be a rather poor implementation of StringBuilder if it couldn't append in O(n) time.)

D M
  • 1,410
  • 1
  • 8
  • 12
  • 1
    It's most likely even faster than that; it could use something like a `LinkedList` for O(1) appending. – Jacob G. Apr 15 '17 at 15:11
  • 1
    I'm not sure about that. If it's O(1) that means you're copying the linked list itself instead of the values - and wouldn't you then run into problems if you wanted to append something to the end? It would change the original. – D M Apr 15 '17 at 15:35