This method has only O(n) , because if you run it with 5, it will go into recursion with 4, then with 3, etc.
Unsigned func (unsigned n) { if (n ==0) return 1; if(n==1) return 2; \\do somthing(in O(1) ) return 2*func(n-1); }
However, what about this:
Unsigned func (unsigned n) { if (n ==0) return 1; if(n==1) return 2; \\do somthing(in O(1) ) return func(n-1) + func(n-1); }
As an example, func (5) will execute it first as
5 -> 4 -> 3 -> 2 -> 1
Then it returns to 2, but there it will complete the "second" part, so the whole process looks like
5 -> 4 -> 3 -> 2-> 1; 2-> 1; 3->2->1; etc.
Therefore, it significantly changes the complexity from O(n) to O(2^n)
Let's try a practical example of this code:
public class Complexity { private static int counter; public static void main(String[] args) { for (int i = 0; i < 20; i++) { counter = 0; func(i); System.out.println("For n="+i+" of 2*func the number of cycles is " + counter); counter = 0; func2(i); System.out.println("For n="+i+" of func + func the number of cycles is " + counter); } } public static int func(int n) { counter++; if (n == 0) { return 1; } if (n == 1) { return 2; } return 2 * func(n - 1); } public static int func2(int n) { counter++; if (n == 0) { return 1; } if (n == 1) { return 2; } return func2(n - 1) + func2(n - 1); } }
Having this conclusion:
For n=0 of 2*func the number of cycles is 1 For n=0 of func + func the number of cycles is 1 For n=1 of 2*func the number of cycles is 1 For n=1 of func + func the number of cycles is 1 For n=2 of 2*func the number of cycles is 2 For n=2 of func + func the number of cycles is 3 For n=3 of 2*func the number of cycles is 3 For n=3 of func + func the number of cycles is 7 For n=4 of 2*func the number of cycles is 4 For n=4 of func + func the number of cycles is 15 For n=5 of 2*func the number of cycles is 5 For n=5 of func + func the number of cycles is 31 For n=6 of 2*func the number of cycles is 6 For n=6 of func + func the number of cycles is 63 For n=7 of 2*func the number of cycles is 7 For n=7 of func + func the number of cycles is 127 For n=8 of 2*func the number of cycles is 8 For n=8 of func + func the number of cycles is 255 For n=9 of 2*func the number of cycles is 9 For n=9 of func + func the number of cycles is 511 For n=10 of 2*func the number of cycles is 10 For n=10 of func + func the number of cycles is 1023 For n=11 of 2*func the number of cycles is 11 For n=11 of func + func the number of cycles is 2047 For n=12 of 2*func the number of cycles is 12 For n=12 of func + func the number of cycles is 4095 For n=13 of 2*func the number of cycles is 13 For n=13 of func + func the number of cycles is 8191 For n=14 of 2*func the number of cycles is 14 For n=14 of func + func the number of cycles is 16383 For n=15 of 2*func the number of cycles is 15 For n=15 of func + func the number of cycles is 32767 For n=16 of 2*func the number of cycles is 16 For n=16 of func + func the number of cycles is 65535 For n=17 of 2*func the number of cycles is 17 For n=17 of func + func the number of cycles is 131071 For n=18 of 2*func the number of cycles is 18 For n=18 of func + func the number of cycles is 262143 For n=19 of 2*func the number of cycles is 19 For n=19 of func + func the number of cycles is 524287
But if you remember the already calculated results, the complexity is still O(n) even with the second approach:
public class Complexity { private static int counter; private static int[] results; public static void main(String[] args) { for (int i = 0; i < 20; i++) { counter = 0; func(i); System.out.println("For n="+i+" of 2*func the number of cycles is " + counter); counter = 0; func2(i); System.out.println("For n="+i+" of func + func the number of cycles is " + counter); counter = 0; results = new int[i+1]; func3(i); System.out.println("For n="+i+" of func + func with remembering the number of cycles is " + counter); } } public static int func(int n) { counter++; if (n == 0) { return 1; } if (n == 1) { return 2; } return 2 * func(n - 1); } public static int func2(int n) { counter++; if (n == 0) { return 1; } if (n == 1) { return 2; } return func2(n - 1) + func2(n - 1); } public static int func3(int n) { counter++; if (n == 0) { return 1; } if (n == 1) { return 2; } if (results[n] == 0){ results[n] = func3(n - 1) + func3(n - 1); } return results[n]; } }
Having this conclusion:
For n=0 of 2*func the number of cycles is 1 For n=0 of func + func the number of cycles is 1 For n=0 of func + func with remembering the number of cycles is 1 For n=1 of 2*func the number of cycles is 1 For n=1 of func + func the number of cycles is 1 For n=1 of func + func with remembering the number of cycles is 1 For n=2 of 2*func the number of cycles is 2 For n=2 of func + func the number of cycles is 3 For n=2 of func + func with remembering the number of cycles is 3 For n=3 of 2*func the number of cycles is 3 For n=3 of func + func the number of cycles is 7 For n=3 of func + func with remembering the number of cycles is 5 For n=4 of 2*func the number of cycles is 4 For n=4 of func + func the number of cycles is 15 For n=4 of func + func with remembering the number of cycles is 7 For n=5 of 2*func the number of cycles is 5 For n=5 of func + func the number of cycles is 31 For n=5 of func + func with remembering the number of cycles is 9 For n=6 of 2*func the number of cycles is 6 For n=6 of func + func the number of cycles is 63 For n=6 of func + func with remembering the number of cycles is 11 For n=7 of 2*func the number of cycles is 7 For n=7 of func + func the number of cycles is 127 For n=7 of func + func with remembering the number of cycles is 13 For n=8 of 2*func the number of cycles is 8 For n=8 of func + func the number of cycles is 255 For n=8 of func + func with remembering the number of cycles is 15 For n=9 of 2*func the number of cycles is 9 For n=9 of func + func the number of cycles is 511 For n=9 of func + func with remembering the number of cycles is 17 For n=10 of 2*func the number of cycles is 10 For n=10 of func + func the number of cycles is 1023 For n=10 of func + func with remembering the number of cycles is 19 For n=11 of 2*func the number of cycles is 11 For n=11 of func + func the number of cycles is 2047 For n=11 of func + func with remembering the number of cycles is 21 For n=12 of 2*func the number of cycles is 12 For n=12 of func + func the number of cycles is 4095 For n=12 of func + func with remembering the number of cycles is 23 For n=13 of 2*func the number of cycles is 13 For n=13 of func + func the number of cycles is 8191 For n=13 of func + func with remembering the number of cycles is 25 For n=14 of 2*func the number of cycles is 14 For n=14 of func + func the number of cycles is 16383 For n=14 of func + func with remembering the number of cycles is 27 For n=15 of 2*func the number of cycles is 15 For n=15 of func + func the number of cycles is 32767 For n=15 of func + func with remembering the number of cycles is 29 For n=16 of 2*func the number of cycles is 16 For n=16 of func + func the number of cycles is 65535 For n=16 of func + func with remembering the number of cycles is 31 For n=17 of 2*func the number of cycles is 17 For n=17 of func + func the number of cycles is 131071 For n=17 of func + func with remembering the number of cycles is 33 For n=18 of 2*func the number of cycles is 18 For n=18 of func + func the number of cycles is 262143 For n=18 of func + func with remembering the number of cycles is 35 For n=19 of 2*func the number of cycles is 19 For n=19 of func + func the number of cycles is 524287 For n=19 of func + func with remembering the number of cycles is 37