it is O(n) actually we use memoization in recursion to avoid calculating same subproblem.
On Wed, Sep 14, 2011 at 9:38 PM, tech coder <[email protected]>wrote: > > an interseting problem > > for a fibonacci series > the recurrence relation is > t(n)=t(n-1)+t(n-2)+O(1) > on solving it gives upper bound of O(n^2) > > but when draw tree for the recurcsion we see that it is growing > exponentially giving a complexity of O(2^n). > > so what is the complexity for fibonaacci series n^2 or 2^n > > -- > * > > Regards* > *"The Coder"* > > *"Life is a Game. The more u play, the more u win, the more u win , the > more successfully u play"* > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
