Geek Answers Handbook

Difficulty for recursive functions - time and space

I was interested to learn how to calculate the temporal and spatial complexity of recursive functions such as permutation, fibonacci (described here )

In general, we can have recursion in many places, not just permutation or recursion, so I'm looking for an approach that is usually used to calculate complex space complexity

thanks

+4
source share
2 answers

Time complexity and space complexity are two things that characterize algorithm performance. Currently, since space is relatively inexpensive, people are often worried about the complexity of time, and time complexity is mainly expressed in relation to the repetition ratio.

Consider the binary search algorithm (search for an element in an array): each time the middle element (middle) is selected and compared with the element (x) to be searched. If (mid> x), find the bottom submatrix, otherwise search in the upper submatrix. If the array contains n elements, and let T (n) represent the time complexity of the algorithm, then T (n) = T (n / 2) + c, where c is a constant. Under given boundary conditions, we can solve for T (n), in this case T (n) = log (n), and T (1) = 1.

+2
source

More articles:


All Articles