2

Consider using something like

StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i++){
  sb.append('a');
}

Is the efficiency of the code O(N^2) or O(N)?

Based Tyrone
  • 41
  • 6
  • 2
    Possible duplicate of [What is the complexity of this simple piece of code?](https://stackoverflow.com/questions/7156122/what-is-the-complexity-of-this-simple-piece-of-code) – erip Jun 08 '17 at 01:13
  • You might want to pre-allocate the capacity e.g.: `StringBuilder sb = new StringBuilder(n);` This is true for most dynamically sized arrays or lists. Without pre-allocation you're depending on automatic reallocation that could come every log(n) cycles, or every n cycle. slowing you to `O(n*log(n))` or even `O(n^2)`. – ebyrob Jun 08 '17 at 01:16
  • 3
    A long way to write [`StringUtils.repeat('a', n);`](https://commons.apache.org/proper/commons-lang/apidocs/org/apache/commons/lang3/StringUtils.html#repeat-char-int-) is how I would describe it. – Elliott Frisch Jun 08 '17 at 01:34
  • @ebyrob, no, automatic reallocation can't slow you above O(n). At most it's going to be O(n + n/2 + n/4 + ...) = O(2n) = O(n). – Louis Wasserman Jun 08 '17 at 03:28
  • @LouisWasserman at worst I was expecting reallocation taking `i` operations every single loop but I admit I'm a bit weak on big O notation. that would be O(n + 1 + 2 + 3 + 4 ... + n) which would be `n * (n+1)/2` operations. But you're right if doubling the size every realloc that would only be `O(log(n)*log(n))` or `O(n)` not `O(n*log(n))` as I said earlier. Still I think when relying heavily on array reallocation, it's important to know something about the implementation. Different platforms use different growth factors. https://en.wikipedia.org/wiki/Dynamic_array – ebyrob Jun 08 '17 at 15:33
  • -shrug- regardless of the growth factor, as long as it's a constant multiplicative factor the whole thing will still be O(n). – Louis Wasserman Jun 08 '17 at 15:52

1 Answers1

0

It is O(N), meaning it takes the cost of how big you n variable is.

developer_hatch
  • 15,898
  • 3
  • 42
  • 75