CODEWITHSUNDEEP
javarecursionmethodscomplexity-theory
duketwo
duketwo

Reputation: 5643

Java complexity of two recursive methods

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

Upvotes: 4

Views: 259

Answers (3)

RealSkeptic
RealSkeptic

Reputation: 34618

(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.

Upvotes: 3

S. Pauk
S. Pauk

Reputation: 5318

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.

Upvotes: 0

Paul Boddington
Paul Boddington

Reputation: 37645

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.

Upvotes: 3

Related Questions