Skip to main content

Recursive Algorithms

Understanding Recursive Algorithm Run Time & Space Complexity

Time Complexity​

In recursive algorithms determing the time complexity is defined as follows:

Time Complexity = (Depth of Recursion/Call Stack) × (Work Done per Call) % Time Complexity=(Depth of Recursion)×(Work Done per Call) \text{Time Complexity = (Depth of Recursion/Call Stack) × (Work Done per Call)}

Time Complexity Examples​

If the depth of stack is in the worst case O(n)O(n) and in each execution we also do O(n)O(n) work then it would O(n2)O(n^2)

O(n)∗O(n)=O(n2)O(n) * O(n) = O(n^2)

If the depth of stack is O(log⁡n){O}(\log{}n) but we do O(n)O(n) work in each execution then the time complexity is O(nlog⁡n){O}(n\log{}n)

O(log⁡n)∗O(n)=O(nlog⁡n){O}(\log{}n) * O(n) = {O}(n\log{}n)

Space Complexity​

In recursive algorithms determing the space complexity is defined as follows:

Space Complexity = (Depth of Recursion) × (Space Required per Call) % Space Complexity=(Depth of Recursion)×(Space Required per Call) \text{Space Complexity = (Depth of Recursion) × (Space Required per Call)}

Space Complexity Examples​

If we have an algorithm with a depth of call stack of O(log⁡n){O}(\log{}n) but in each stack we have O(1)O(1) space, it would be O(log⁡n){O}(\log{}n)

O(log⁡n)∗O(1)=O(log⁡n){O}(\log{}n) * O(1)= {O}(\log{}n)

Whereas if depth is O(log⁡n){O}(\log{}n) but in each call we allocate O(n)O(n) space it would be O(nlog⁡n){O}(n\log{}n) space

O(log⁡n)∗O(n)=O(nlog⁡n){O}(\log{}n) * O(n) = {O}(n\log{}n)