Reccurence Relation

user_18598205 0
Viewed 28

I have a method:

int Tree (int n) { 
  if (n <= 0) return 0; 
  if (n == 1) return 1; 
  return ((n*n) + Tree (n-3)); 
}

I'm trying to find the recurrence relation that captures the running time T(n) for the method 'Tree', so far I've got T(n) = T(n-3) + O(1), then I will need to express the running time as a series of terms, where each term denotes the number of operations at a distinct level of the recursion tree:

I have T(n) = T(n-3) + O(1) then T(n-1) = T(n-4) + O(1) then T(n-2) = T(n-5) + O(1) ... But Im unsure if this is right

recurrence recursion big-o time-complexity
1 Answers

After T(n) = T(n-3) + O(1) you don't need to check T(n-1) but T(n-3) which is = T(n-6) + O(1). Replacing n by 3p+r you get T(3p+r) = T(3(p-1)+r)+O(1) which gives T(3p+r)=T(r)+O(p), Since T(r) = O(1) and O(p) = O(n), T(n) = O(n)

user_42863250
Related