Algorithmic complexity of iterative - recursive solution

Question

I had an exam of algorithms and data structures today and I was given an excercise I wasn't prepared for. The excercise was some pseudocode that we needed to extrapolate the time complexity out of.

The entire crux of the doubt lies on a particular part of the code :

recursive_call(int n){
 if(n > 1){
    int t = 0;
    for a in 1 to n do
       t = t + (a*2) * (a*3)

    for a in 1 to 7 do 
       acc = acc + recursive_call(n/3)
    return acc; 
 }
  else return n-1;
}

The first part is trivially linear : the loop is executed n times. The second part , me and the rest of my group are in disagreement.

According to some , the complexity is actually T(n) = T(n / 3) + O(n). The recursive call is not splitted in multiple calls on the same activation record , hence it's never divided , therefore T(n/3) is not multiplied by any a>1.

Personally, I think that it doesn't matter on which part of the input you're calling the recursion , as long as you are doing it multiple times , it counts. Therefore the function should be T(n) = 7T(n/3) + O(n), because the function gets called multiple times. The fact that the input is identical is irrelevant.

So we are at an impasse. Can anyone clear this up?

Answer 1

The second variant is correct - complexity for this implementation satisfies $T(n) = 7 T(\frac{n}{3}) + O(n)$.

It's possible to optimize this implementation by making recursive call only once, but it will formally be another algorithm with different complexity.