Time complexity of recursive function - Single recursive call of size n/3 and n^2 loop

Question

function T(int n) {
  int n1 = 2T(n/3) + 5
  int n2 = 2*n1*n1
  int sum = 0 

  for i = 1 to n {
    for j = 1 to n {
      sum+=n1*i + n2*j
    }
  }
  return sum
}

// Assume T(1) = 1

T(n) = ?

Answer 1

T(n/3) is a one-time recursive call, work just for n1.  There is no other recursive call.  And the nested-loop takes Theta(n^2) time. From this, we get the following recurrence relation:

T(n)=T(n/3)+n^2;

using Master Theorem:

T(n)=n^2;

Comments

I didn't seem straightforward to me, and I guess a bit explanation would be helpful for following readers like me: calculating T(n/3) is an one-time work just for n1, meaning the following n2 or sum do not call T(n) again - they use n1. :) And the nested-loop takes Theta(n^2) time. That's how we get T(n)=T(n/3)+n^2.