Loading collection data...
Collections are a way for you to organize kata so that you can create your own training routines. Every collection you create is public and automatically sharable with other warriors. After you have added a few kata to a collection you and others can train on the kata contained within the collection.
Get started now by creating a new collection.
This comment is hidden because it contains spoiler information about the solution
Not efficient, but he use primitive types, not wrapper class. Is valid solution.
not efficient
if someone new is having doubt here go read about String pool, basically in each concatenation a new string object is created and it consumes way too much memory
@olee2002 It's good that you benchmarked it! There are a couple possibilities.
Microbenchmarks in Java are notoriously difficult.
As you suggested, the O(n^2) version could very well be faster for small n.
Note that strings in Javascript are also immutable, so you get the same situation. The solution is less clear, but I think
string.join
is an O(n) solution in JS. "Naive" concatenation with+
in JS may use something like StringBuilder under the hood depending on the browser engine (but I wouldn't count on it), whereas in Java it's guaranteed to be O(n^2).I am a newbie to Java but interestingly this solution runs faster than the StringBuilder. I tried to run them both to see which one runs faster. But I guess its because the string isn't long enough? I am from the Javascript land so I was excited to see this approach since this looks close to JS.
Because a String object can't be changed. In this code in the line "s+=string;" a new string is created every iteration.
Concatenation takes time relative to the lengths of the input strings. The left side of the concatenation carries all previous concatenations with it, so you get a total time on the order of (1 + 2 + 3 + ... + repeat) = (repeat * (repeat + 1) / 2) which is O(n^2), n = repeat.
Concatenations on a StringBuilder are constant time amortized. So the result is 1 + 1 + ... + 1, repeat times. O(n).
I know that (and why) StringBuilder is faster, but how does this solution run in O(n^2)?