Can anyone help understanding a recurrence relation?

Question

I'm learning about time complexity and have this function:

public static double pow( double x, int n ) {
    if( n==0 ) return 1.0;
    return x*pow(x,n-1); 
}

I'm tasked with finding the recurrence relation for it's time complexity and I know the answer is T(n) = T(n-1) + O(1), which I don't understand because I think it should be T(n) = T(n-1) + O(n). My reasoning is that I multiply each recursive call with x which happens n times so that's O(n) right?

*edit: I think I understand my mistake. T(n) = T(n-1) + O(1) is only for that specific call so it's clearly O(1) and solving the recurrence leads to n*T(n-1) + (n-1)O(1) so the (n-1)O(1) is ignored since it's less than n*T(n-1). So we get order of growth = O(n).

Answer 1

You don't need to consider every multiplication. Recurrence relations are about how the call for one number relates to the same call for a different number. In this case, calculating pow(x,n) requires that you already know pow(x,n-1) - that's the T(n) = T(n-1) part. Now, what do you additionally need to do to calculate pow(x,n), given that you already have pow(x,n-1)? That's only a single multiplication - x*pow(x,n-1) - which is O(1), so the total recurrence relation is T(n) = T(n-1) + O(1). All the other multiplications are already accounted for in T(n-1)...