Рекуррентное отношение следующей функции

Question

Я пытаюсь определить рекуррентное отношение следующей рекурсивной функции.. Я думаю, что я сделал это правильно, но хотел бы получить некоторую информацию о моем методе решения..

Solve for C(n) the number of additions that this function does:
  //precondition: n>0
 int fct (const int A[], int n) {
      if (n==1)
         return A[0]*A[0];
      else return A[n-1] * fct(A,n-1) * A[n-1];
 } 

Здесь происходит ровно два добавления, а также рекурсивный вызов для n-1. C(1)=1 C(n)=2+C(n-1) //2 из-за количества добавлений плюс рекурсивный вызов C (n-1)

Следовательно

C (2) = C (1) + 2 = 1 + 3 = 3 C (3) = C (2) + 2 = 2 + 3 = 5 C (4) = C (3) + 2 = 7 C (n) = 2n-1

где большой o это O(n)?

Answer 1

Правильный. Имейте в виду, что структура рекурсивной функции зависит от n:

int addRec(int A[], int n) {

В остальном сложения имеют постоянное время, поэтому вы выполняете постоянную операцию n раз, что приводит к сложности O(n) времени, которую вы получили.