When you are considering the complexity of a method that calls a recursive method (a primer method), do you consider the complexity of the recursive method, or just consider the call of the method.
For example, I have a small program that calculates a fibonacci sequence:
// Complexity: ???
public int fib() {
int n = 9;
return fib(n);
}
// Complexity: O(2^n)
private int fib(int n) {
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
The complexity of the recursive fib(int n) method is O(2^n), but I am not sure what the complexity of fib() would be.
My assumption is that it is complexity 1 because all it does is define and int and return a number.
My assumption is that it is complexity 1 because all it does is define and int and return a number.
As a statement of fact, your "all its does ..." it is not true. The value of f(9) is being computed as well. (It could be computed at "compile time", but it is being computed nonetheless.) Since the premise of your argument is not strictly correct ... no conclusion can be adduced.
Ignoring that quibble, your explanation is intuitively correct but it does not stand up from a rigorous mathematical perspective.
A better explanation is to pick some mathematical variable (say Q). We can then say that the time complexity of fib() is O(1) with respect to that variable.
(Note that n is not a variable in this context, any more than pi or e are variables.)
Or you could say that a complexity analysis of fib() is meaningless unless you identify an input variable of interest.
These two ways of looking at this make more sense from a mathematical perspective (IMO), The accepted mathematical definitions of O assume that there is a variable. The O complexity characterizes the behavior of the function with respect to that variable.