Complexity for recursive functions - Time and Space

Question

I was interested in knowing how to calculate the time and space complexity of recursive functions like permutation, fibonacci(described here)

In general we can have recursion at many places than just at permutaion or recursion, so I am looking for approach generally followed to calculate tmie ans space complexity

Thank you

Solution 1

Take a look at http://www.cs.duke.edu/~ola/ap/recurrence.html

Solution 2

Time complexity and space complexity are the two things that characterize the performance of an algorithm. Nowadays, as space is relatively inexpensive, people bother mostly about time complexity, and time complexity is mostly expressed in terms of a recurrence relation.

Consider binary search algorithm (Search for an element in an array): Each time middle element(mid) is selected and compared with the element(x) to be searched. If (mid > x), search the lower sub-array, otherwise search the upper sub-array. If there are n elements in an array, and let T(n) represents the time complexity of the algorithm, then T(n) = T(n/2) + c, where c is a constant. With given boundary conditions, we can solve for T(n), in this case, it would be T(n) = log(n), with T(1) = 1.

Comments

[2cupsOfTech]

answer is explained visually here: 2cupsoftech.wordpress.com/2012/10/31/…