5

I am currently studying data structures at university and stumbled across a question about complexity in recursion.

Given this code: 

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);
}

I know what the code does. I know that in the form it is now, the time complexity is O(2^n).

My question however is: will the time complexity change if instead of the last return call of the code I will write: return 2*func(n-1) ?

I know that as far as memory complexity, we are talking about a significant reduction in space taken by the recursion, but as far as time complexity, will there be any change?

I did the math using a recursive function and came to the understanding that there will be no change in time complexity, am I right?

Improve this question

2 Answers 2

Reset to default
4

This method is having only O(n), because if you run it with 5, it goes to 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);
}

At for example func(5) it will execute first as following 

5 -> 4 -> 3 -> 2 -> 1

Then it returns to 2, but there it will execute the "second" part, so the whole process looks like 

5 -> 4 -> 3 -> 2-> 1; 2-> 1; 3->2->1; etc.

Therefore it DOES change complexity drastically from O(n) to O(2^n)

Lets try practical example 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 output :

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 already computed 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 output :

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
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

So was I right that the recursive call of func(n-1) + func(n-1) is running at a complexity of O(2^n)? also, how come that on my recursion formula, when I write it on paper and calculate, I get that both of them are having the same time complexity?
@Tom - yes, it runs at complexity O(2^n)... about your formula - you are using it wrong or you have wrong formula. Post that formula to your question and maybe we can tell you whats wrong.
My formula is: T(n) = 2T(n-1) while T(0)=1,T(1)= 2. I used the "posting method" and got to the general function: T(n) = 2^i *T(n-i). after postioning my stopping conditions such as i = n-1 or i = n-2, I reached the complexity of T(n) = 2^(n-1) *T(1) = (2^n)/2 -------> O(2^n). the same result for the other stopping condition. what am I doing wrong, as I was getting the same formula for both types of code.
T(n) = 2T(n-1) is not right in 2*func(n-1), because T(n) does not do T(n-1) twice, it do it only once and then multiply the result by two, which is different thing.
could you please help me then to write the right T(n) for the 2*func(n-1) scenario? how do I simulate the fact that it does the call only ones and then multiples the result by 2?
|
2

It depends on the semantic of your programming/algorithm language.

If by f(n) you mean "call the function no matter if it was called with the same argument before" (as it is the case with most programming languages), then your change will reduce the complexity dramatically to O(n). You have one O(1) function call per decrement of the argument.

Otherwise (if you are speaking about pure functions and memoizing known results), both algorithms have complexity O(n) already.

Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.