Re: Complexity Evaluation
A bit late, but the key insight is that you can express the solution as a recurrence relationship. Namely the complexity for some value of n (let's call it C(n)) is:
C(n) = n * C(n/3) subject to C(1) = 1
This is because the loop runs n times with worst-case complexity of C(n/3) per iteration.
Actually this is an overestimate. The real complexity relationship is:
C(n) = Sum[ C(i/3) ] for i in [1, n]
but this will be a pain to deal with. The overestimate will be reasonable.