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)
...
Can anyone help understanding a recurrence relation?
-
10-10-2022 - |
Вопрос
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).
Решение
Не связан с StackOverflow