CODEWITHSUNDEEP
kotlintime-complexity
rafi
rafi

Reputation: 316

Time complexity of Int.toString() in kotlin

I want to know the time complexity of the default method toString() in kotlin. Is it O(1) or O(n).I have done some searching but didnt find any answer. For example: if I want to convert an array of int to a String, I have used:

var s = ""
array.forEach{
  s+= it.toString()
}

But I'm getting TLE if the array size is 10^4. if i dont use toString() then I dont get TLE.I know there are others way to convert an array of Int into String. But I want to know the time complexity of default toString() method in kotlin. TIA

Upvotes: 0

Views: 501

Answers (1)

gidds
gidds

Reputation: 18627

Kotlin makes no guarantees about the complexity of toString().

It probably varies between objects; every object has to implement it, and so it's likely to depend on the structure of the object and of its string representation.  In many cases, I'd guess it's likely to be linear in the length of the string, but you shouldn't rely on that.  But it does mean that objects with a short string representation are likely to take little enough time that it's not worth worrying about.

In particular, for Ints it's very probably linear in the size of the string (and hence proportional to the logarithm of the number).  But that's not likely to be significant for any real-world program.

However, what is likely to be significant is the number of String objects constructed, since those take memory, and then hasten the next garbage collection.  (Even for garbage collectors that take the same time regardless of the number of ‘dead’ objects, having lots of temporary objects will cause them to run more often.  In a high-throughput system, that can be really significant.)

That's certainly an issue for the code in the question, which creates two new String instances each time round the loop!  One is the result of calling toString(); the other is the result of appending that to s.  (And while the former will always be small, the latter will grow and grow each time, which makes this quadratic in space requirement.)  That's why it's usually a bad idea to do string concatenation in a loop!

Of course, String is immutable — but it has a mutable helper class, StringBuilder.  So it's almost always better to use a StringBuilder to accumulate the results, and then create a String (if needed) at the end:

val sb = StringBuilder()
array.forEach {
  sb.append(it.toString())
}
val s = sb.toString()

In this case you can do even better than that, because StringBuilder overloads append().  So you can append an Int directly, without creating an intermediate String at all:

val sb = StringBuilder()
array.forEach {
  sb.append(it)
}
val s = sb.toString()

The only temporary objects that that creates are the StringBuilder's internal arrays; as the contents grow and grow, it will need to reallocate its array to hold them.  If you can estimate the size of the final result, you can pre-size the StringBuilder to avoid even that overhead.

In practice, though, you probably wouldn't use a loop at all; you'd use joinToString(), which does all that for you:

val s = array.joinToString("")

That's shorter, simpler, easier to read, and likely to perform as well as a hand-coded version.  Kotlin has a lot of useful extension functions; it's well worth getting familiar with them!

And in cases where you need to construct a complex string representation yourself as efficiently as possible, instead of using toString() to create each part, each relevant class can have a method that takes a StringBuilder as a parameter, and appends its part to that.  That can let you build up an arbitrarily complex string without any String instances at all!

Upvotes: 2

Related Questions