1
String s ="";
for (int i = 0; i < n; i++) {
    if (StdRandom.bernoulli(0.5)) s += "0"; 
    else                          s += "1"; 
}

StringBuilder sb = new StringBuilder(); 
for (int i = 0; i < n; i++) {
    if (StdRandom.bernoulli(0.5)) sb.append("0"); 
    else                          sb.append("1");
}
String s = sb.toString();

I don't understand why the first is quadratic and the second is linear. It's one of the exersizes of the chapter 4 of the book <Computer Science · An Interdisciplinary Approach>.

Daniel
  • 7,357
  • 7
  • 32
  • 84
Chen
  • 11
  • 2
  • 1
    Does this answer your question? [String concatenation complexity in C++ and Java](https://stackoverflow.com/questions/15400508/string-concatenation-complexity-in-c-and-java) – Putnam Jul 14 '20 at 03:19
  • Related: https://stackoverflow.com/questions/1532461/stringbuilder-vs-string-concatenation-in-tostring-in-java – Jerry Jeremiah Jul 14 '20 at 03:20
  • @muru that post has zero votes, and has no accepted answer. If there is a particular one of the answers you thought was insightful, better to link to that answer rather than suggest this is a duplicate. – Mike 'Pomax' Kamermans Jul 14 '20 at 04:00
  • @Mike'Pomax'Kamermans O.o neither of those are disqualifying aspects to being a duplicate candidate. – muru Jul 14 '20 at 04:16
  • No, but the idea behind duplicates is that you're pointing everyone (not just the person doing the asking, but also all future visitors who find this question either through SO search or Google etc) to a prior, authoritative question-and-answer. As such, pointing at a question _without_ an accepted answer should really only be your last resort (and of course, sometimes it's the only option, but that's really quite rare). – Mike 'Pomax' Kamermans Jul 14 '20 at 21:55

0 Answers0