find recursive time complexity of fibonacci series by substitution method

Question

what is time comlexity procedure for following recursive equation by substitution method:

T(n)= T(n-1)+T(n-2) , if n>=2

      =1 , if n=1;

      =0 , if n=0.

Answer 1

by naive fibonacci algo its sigma(c2pow(n/2))

 

by clever algo its 0(n2)

naive sol

T(n)=T(n-1)+T(n-2)

    >=2T(n-2)+c

   .......

>=2 pow(k)T(n-2.k)+c(2pow(k-1)+2pow(k-2)+.........+1)

sigma(c2pow(n/2))