What is the time complexity of recursive fibonacci without memoization?
O(2^n) - exponential. Each call makes two recursive calls, creating a binary tree of calls. Many calls are redundant (fib(3) is computed multiple times). Memoization reduces this to O(n).
Verify This Answer
Cross-check this information using these trusted sources:
More FAQs in Recursion Interview Questions in JavaScript
const memo = {}; function fib(n) { if (n < 2) return n; if (memo[n]) return memo[n]; return memo[n] = fib(n-1) + fib(n-2); }. Memoization reduces time from O(2^n) to O(n).
function flatten(arr) { return arr.reduce((acc, item) => acc.concat(Array.isArray(item) ? flatten(item) : item), []); }. If an item is an array, recurse. Otherwise, concatenate.
function traverseDOM(node, callback) { callback(node); Array.from(node.children).forEach(child => traverseDOM(child, callback)); }. Call the callback on the current node, then recurse into each child.
Still have questions?
Browse all our FAQs or reach out to our support team