I need to know how to calculate the complexity of this algorithm using the recurrence equation.
public int qdr(int x, int n) {
if(n == 0)
return 1;
else
return x * qdr(x, n-1);
}
It is a recursive algorithm that reads two numbers x and n and returns the result of x ^ n
and very simple:)
When n > 1 , the function does an operation that has constant time, multiplication, and makes a recursive call that has size n - 1 .
so the recurrence is:
T(n) = T(n-1) + 1 (ou O(1), da na mesma)
T(1) = 1
If you solve it you will get a sum of type 1 + 1 + 1+ ... + 1 , with n uns. that of n . so the function is linear, O(n) .