How to determine the running time T(n) for a given recursive function?

Question

How to determine the recurrence formula of T(n) for the next function?

if(N == 0)
  return 1;

s = 0;

x = function(N/3);

for(i = 1; i <= N; i++){
  s += x;
}

return s;

Answer 1

You can identify a recursive call x = function(N/3) which complexity is T(n/3). What follows are N additions, so N operations to account for.

Therefore the recurrence relation for the complexity of this function is

T(n) = T(n/3) + n

Hence

T(n) = O(n.log3(n))