Do you know what a recurrence relation? Basically, it is a function that is defined in terms of itself. Recurrence relations are the basic tool for solving the exact time-complexity (using Big-Oh notation) for recursive functions. I don't know if your instructor intends to get this specific, although I think
you should.
Grant is correct that this algorithm is O(2^n). To solve this, we can write a mathematical function that models the return value of the method:
f(n) = 2, if n = 0
f(n) = 3 + 2*f(n-1), if n > 0
Note that the recursive case is defined in terms of the function itself (with a smaller value as the "argument"). This is the basic idea of a recurrence relation. In fact, recurrence relations are exactly like recursive methods in programming. (This is no coincidence.)
To solve the problem, first note that the base case is basically irrelevant since it is a constant. The interesting part happens with the recursive case. We manipulate the recursive case to get an equivalent equation:
f(n) - 2*f(n-1) = 3
Then, you create what is called the "characteristic polynomial". From the left, we get (x - 2) by using the coefficients of each f(n) term with decreasing values of n replaced by decreasing powers of x. In other words, f(n) is replaced by x^1 = x and -2*f(n-1) is replaced by -2*x^0 = -2. If we had f(n-2), then f(n) would be replaced by x^2 and on down.
The right hand side can be written as 3*1^n (because 1^n = 1). Notice that 3 is a polynomial of degree 0. So this means that we get (x - 1)^1 = (x - 1). The 1 inside the parentheses comes from 1^n and the 1 in the exponent comes from the degree of the polynomial plus 1 (i.e. 0 + 1 = 1).
Now we multiply (x - 2) and (x - 1) and set it equal to zero:
(x - 2)(x - 1) = 0
This means that x = 2 or x = 1. Now we can write a solution of f(n) in terms of n only, and not in terms of the function itself:
f(n) = c1 * 2^n + c2 * 1^n
The 2 and 1 come from the solutions that we found for x in the characteristic polynomial. In problems like this, you always put it in the form x^n where x is a solution to the characteristic polynomial. Also, c1 and c2 are arbitrary constants that depend on the initial value (i.e. f(0) = 2). If you want, you can solve for c1 and c2, but it isn't necessary if you are only intersted in the Big-Oh.
First we should simplify f(n) to
f(n) = c1 * 2^n + c2
since 1^n = 1 for all n.
Now you should be able to see that f(n) is O(2^n) as Grant said.
I bet this is clear as mud. I will be glad to work on a clearer explanation. Feel free to contact me privately if you want me to go over this with you some more.
Layne