Come hai impostato la relazione di ricorrenza? Hai usato il metodo dell'esperto (o "principale")? Se sì, in quale dei tre casi ti ritrovi? Dal risultato che hai scritto direi che hai verificato il primo... ma a me non sembra che siano soddisfatte le ipotesi di quest'ultimo...

la relazione di ricorrenza dovrebbe essere

F(N) = 1 se N<=1
e
F(N) = 2[F(N/3)] + N se N>1

direi piuttosto che siamo nel terzo caso del teorema e non nel primo.