CODEWITHSUNDEEP
mathrecursionrecurrence
manish mallavarapu
manish mallavarapu

Reputation: 33

Recurrence relation for basic operation

I need a little help with creating a recurrence relation for the Basic Operation for the following recursive algorithm: 

int D(int n) {
  if (n==0) {
    return 0;
  }
  return D(n - 1) + D(n - 1);
}

I think the basic operation for this is addition but I am having trouble setting up the recurrence relation

Upvotes: 0

Views: 637

Answers (1)

Prune
Prune

Reputation: 77837

Are you sure this is the correct code? The recurrence relation is

D(n) = 2 * D(n-1)
base case D(n) = 0

Do you see how this works? The function's recursion step shows you the recurrence step; the function's termination clause shows you the base case.

I'm worried because in closed form, this is

D(n) = 0 for all n

Upvotes: 1

Related Questions