TIME COMPLEXITY IN RECURSION

#1

I’VE NOT UNDERSTOOD TWO THINGS IN THIS , KINDLY EXPLAIN.

  1. WHY T(N-1) app= T(N-2)?
  2. for the fibonacci if we take N>20 , why it give TLE ?

Please explain these two things thoroughly?

#2

Hey @CODER_JATIN
Time complexity is O(XYZ) here it means that XYZ is upper bound on complexity
Now fibonacci is
T(n)=T(n-1)+T(n-2)
==>T(n) <= 2*T(n-1) (Not approximated exactly just added inequality)
And do on we get
T(n) <=2^n *T(1) <=2^n
Hence O(2^n)

You will get TLE when N>26 for N<=26 it will work (sir just approximtely gave an idea)
because 2^n when n>=27 becomes more than 10^8 and u can only do 10^8 operations in 1 second.

#3

bhaiya , first wala doubt ni cler hua bhai, second to smjh aa gya ki 1 second mai maximum 10^8 operations ho skte hai.

#4

Yaar jo time compexity O ki terms m hoti h na usse upper bound khte h like usse kam hogi hamesha
Toh Fibonacci ka hota h
T(n)=T(n-1)+T(n-2)

Ab this exprn will always be less than 2*T(n-1) [kyuki ham toh zyada hi operation kr rhe h
toh T(n) <= 2*T(n-1)
Toh ab ham similarly likh skte h
T(n-1) <=2*T(n-2)
and so on
Toh jab substitute krte jaoge toh millega
T(n) <=2^n T(1) <=2^N
Hence T(n) ==O(2^n)