Understanding this Time Complexity issue (Cracking the coding interview)

Question

Question:

String joinWords(String[] words) {
    String sentence = "";

    for (String w : words) {
        sentence = sentence + w;
    }

    return sentence;
}

So the solution of this is O(xn^2)

From what I understand, for every iteration, the amount of letters in the variable 'sentence' increases by one. Which, I think, will be O(n^2)?

Is the 'x' just the number of letters in 'words' array?

Answer: On each concatenation, a new copy of the string is created, and the two strings are copied over, character by character. The first iteration requires us to copy x characters. The second iteration requires copying 2x characters. The third iteration requires 3x, and so on. The total time therefore is O(x + 2x + ... x nx). This reduces to O(xn^2)

I'm confused, letters increase by one? You're iterating over an array of words, once. — Dave Newton, Jun 19 '18 at 22:31
First of all, you need to use StringBuilder. And as far as complexity is concerned, it will simply be O(N) where N is the length of all words combined — arahant, Jun 19 '18 at 22:38
@arahant, how come it's O(N), it's O(N^2). On every iteration, a new string of (sentence + w).length() is created (for JAVA). — Anatolii, Jun 19 '18 at 22:41
@user8035311 1)No it won't. Not if the implementation of String is anywhere near standard. 2)That would be space complexity, not time complexity. — Gabe Sechan, Jun 19 '18 at 22:42
@user8035311 No. On a modern system its constant. A String isn't just a character array these days, its more complex. — Gabe Sechan, Jun 19 '18 at 22:50
@user8035311 Also, when you pass in a list of strings, the N in the big O is based on strings. Not characters. You don't change the base unit like that. — Gabe Sechan, Jun 19 '18 at 22:52
Any variables used in the solution, such as `x` and `n`, should have been defined in either the question or the solution. — user2357112, Jun 19 '18 at 22:54
@bob9123 What is `x`? What is `n`? Without knowing what these mean, this question is meaningless. — k_ssb, Jun 19 '18 at 23:22
Possible duplicate of [Cost of string concatenation](https://stackoverflow.com/questions/24111433/cost-of-string-concatenation) — k_ssb, Jun 20 '18 at 02:36
Also answers the question: https://codereview.stackexchange.com/questions/3972/string-manipulation-complexity — k_ssb, Jun 20 '18 at 02:36

score -2 · Answer 1 · edited Jun 20 '18 at 02:10

The answer is wrong in two ways. O(xn^2) doesn't exist. In big O you drop all constants. It would be O(n^2) if that was right (it isn't).

The next part depends on language, the implementation of + on strings and the string class itself. If the string class is mutable, then + should be O(n) assuming it has a decent implementation (doesn't cause a reallocatiion and copy on each use of +). If the string class is immutable, it depends on how the String is implemented- does it use a single character buffer for all data, or can it handle multiple character pointers in an ordered list? Of course even on the worst implementation it wouldn't be O(n^2), more like O(2n) which is O(n) (2 copies per iteration). Anyone giving me an answer of O(n^2) would be marked wrong. But really any modern String class implementation would be O(n) without a constant and be pretty much O(n*l) in space (where n is the number of words and l is the average word length).

class String {
  String base;   //used for appended strings
  String additional;  //used for appended strings
  char baseData[];  //used for pure strings

  String(String base, String additional) {
     this.base = base;
     this.additional = additional;
  }

  operator + (String newString) {
      return new String(this, newString);
  }

   //As an example of how this works
   int length() {
      if(base != null) {
        return base.length()+additional.length(); //This can be cached, and should be for efficiency.
      }
      else {
         return baseData.length;
      }
   }
}

Notice that + is O(1). Yes, I know Java doesn't have operator overloading, the function is there to show how its implemented.

Understanding this Time Complexity issue (Cracking the coding interview)

1 Answers1