Recursive Runtimes

[!INFO]-
topic: 🖥️ Tech
links:

• Big O Notation
• Log N Runtimes

source: Cracking the Coding Interview
tags: #permanent-note #published

Last Modified: =dateformat(this.file.mtime, "MMM. dd, yyyy - HH:mm")

When dealing with recursive algorithms, pay close attention to your space and time complexity. It can easily become O(N²).

If you have a recursive algorithm that makes multiple calls, e.g. calculating the Fibonacci sequence like here, the runtime can be expressed as a tree with 2^N - 1 nodes.

This results in O(2^N).

However, a straight recursion with only one call, like calculating the factorial, only takes O(n).