4
public static String rec1 (String s) {

    int n = s.length()/2; 
    return n==0 ? s : rec1(s.substring(n)) + rec1(s.substring(0,n)); 
}


public static String rec2 (String s) {
    return s.length()<=1 ? s : rec2(s.substring(1)) + s.charAt(0); 
}

Why is the complexity of rec2 greater than rec1?

I've done 10.000 iterations on each and measured the execution time using System.nanoTime() with the following results:

rec1: Stringlength: 200  Avgtime: 19912ns Recursive calls: 399

rec1: Stringlength: 400  Avgtime: 42294 ns Recursive calls: 799

rec1: Stringlength: 800  Avgtime: 77674 ns Recursive calls: 1599

rec1: Stringlength: 1600 Avgtime: 146305 ns Recursive calls: 3199

rec2: Stringlength: 200  Avgtime: 26386 ns Recursive calls: 200

rec2: Stringlength: 400  Avgtime: 100677 ns Recursive calls: 400

rec2: Stringlength: 800  Avgtime: 394448 ns Recursive calls: 800

rec2: Stringlength: 1600 Avgtime: 1505853 ns Recursive calls: 1600

So at a stringlength of 1600 rec1 is 10x faster than rec2. I'm looking towards a brief explanation.

enter image description here

3
  • 1
    What makes you think that the complexity of rec2 is > rec1? Put a print statement in each method and trying running them. For instance, rec1("1234") makes 7 calls whereas rec2("1234") makes 4.
    – azurefrog
    Mar 26, 2015 at 21:05
  • Check my edit above, i measured the time using System.nanoTime and trying to figure the reason why rec2 is faster than rec1. ( Even disabled speedstep )
    – duketwo
    Mar 26, 2015 at 21:52
  • My original answer was wrong. I've now updated. Mar 26, 2015 at 22:23

3 Answers 3

3

According to Time complexity of Java's substring(), String#substring now copies the backing array, so has O(n) time complexity.

Using this fact it can be seen that rec1 has time complexity O(n log n) whereas rec2 has time complexity O(n^2).

Start with an initial String s = "12345678". For simplicity I have taken the length to be a power of 2.

rec1:

  1. s is split into "1234" and "5678".
  2. These are split into "12", "34", "56", "78"
  3. These are split into "1", "2", "3", "4", "5", "6", "7", "8"

There are 3 steps here because log(8) = 3. Every char is copied in every step, so the total number of copied characters is O(n log n). When the String is reassembled in reverse order, the above Strings are now joined together using concatenation, using the following steps:

  1. Strings are joined into "21", "43", "65", "87"
  2. Strings are joined into "4321", "8765"
  3. Strings are joined to make "87654321".

This another total of O(n log n) copied characters!

rec2:

  1. s is split into "1" and "2345678".
  2. "2345678" is split into "2" and "345678".
  3. "345678" is split into "3" and "45678".
  4. "45678" is split into "4" and "5678".
  5. "5678" is split into "5" and "678".
  6. "678" is split into "6" and "78".
  7. "78" is split into "7" and "8".

This is a total of 8 + 7 + 6 + 5 + 4 + 3 + 2 = 35 copied characters. If you know algebra, this will be (n * (n+1)) / 2 - 1 copied characters in general, so O(n^2).

When this is all assembled in reverse order, the number of copies characters will be O(n^2) again.

4
  • 1
    How did you get to O(n log n)? The recursion is called twice in each level. That cancels out the log n, and the total complexity is linear in the number of recursion, multiplied by the copies of the characters. Mar 26, 2015 at 22:37
  • @RealSkeptic I'm reasonably confident I'm right, but I'm going to do some tests to check... Mar 26, 2015 at 22:42
  • Thanks for the excellent answer. Im not sure either if it's O(n) or O(n log n)
    – duketwo
    Mar 26, 2015 at 22:58
  • You're right, and I've corrected my answer accordingly. The key is that each character is copied depth times, regardless of the number of recursion steps. Mar 26, 2015 at 23:39
3

(This is a corrected version regarding time complexity)

Although the number of recursions is actually linear in n (because the recursion is called twice at each level) there is a difference between the two methods as far as copying the characters is concerned.

Each of the methods is internally doing two copy operations - one for the substring (in Java 7), and one for the concat (represented by the + operator).

In rec2, it copies the right side of the string again and again all the way until only one character remains. So the last character in the string is copied depth times, and the depth is linear. So linear steps multiplied by linear copies (it's actually a series) gives O(n2).

In rec1, each character gets either copied to the left substring or the right substring. But no character is copied more than depth times - until we get to the single-character substrings. So each character is copied log n times. Although the recursion is called twice, it is not called on the same characters, so the cancellation of the log caused by the double call does not affect the number of copies of each character.

The same is true for the re-construction. The same copies take place in reverse.

Number of copies - n characters multiplied by depth of log n, gives O(n log n). Number of steps performed - O(n), so the number of steps is less significant than the number of copies, and the total of the complexity is O(n log n).


In addition, there is space complexity. rec1 goes to a depth of O(log n) in its recursion, that is, it takes stack space of O(log n). It does so twice, but that doesn't change the big-O. In contrast, rec2 goes to a depth of O(n).

On my machine, running the two methods with a string of length 16384 resulted in a stack overflow for rec2. rec1 finished without a problem. Of course this varies based on your JVM settings, but you get the picture.

1
  • I needed some visual aid to better understand the question and the finer points in your answer, so I printed the recursive calls: pastebin.com/WAipHBYE Maybe it can help other people as well.
    – vanOekel
    Mar 27, 2015 at 1:24
0

Let's investigate the performance difference:

String.substring() 
  • substring is really cheap in java (up until Java 7 Update 6) cause it doesn't copy the raw data but only updates offsets on the same array.

String overriden + operator

  • here comes the difference cause overriden + operator uses StringBuilder in case of non-literal strings. If you drill down the implementation of StringBuilder.append() method you will finally find a call to System.arraycopy().

So the difference is that System.arraycopy() is dealing with exponentially decreasing array size in rec1 while only with linearly decreasing array size in rec2.

3
  • Thanks for your answer. I measured the execution time of both methods with different length and they behave differently on longer strings, im looking for a reason for this behaviour.
    – duketwo
    Mar 26, 2015 at 21:50
  • I'm not the downvoter, but according to Jon Skeet stackoverflow.com/questions/4679746/… subString does now copy the raw data. Mar 26, 2015 at 22:39
  • i'm currently running JDK 1.7.0.04 and in this version there's no copying for subString. So the difference on my Java version comes mostly from System.arraycopy()
    – S. Pauk
    Mar 26, 2015 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.