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.