Recursion

AP Computer Science A· difficulty 4/5

Recursive Fibonacci with memoization vs naive:

A
$Memoized: O(2ⁿ); Naive: O(n)$
B
$Both O(n)$
C
$Memoized: O(n); Naive: O(2ⁿ)$
check_circle
D
$Both O(2ⁿ)$

Explanation

Caching avoids redundant subproblem solving.

Want 10 more like this — adaptive to your weak spots?

Practice 10 like thisarrow_forward Predict my AP score

Related questions

csa-u910-033
What happens for sum(0)?…
chevron_right
csa-r2-algo-048
How many print statements occur for n=4?…
chevron_right
csa-rec-019
What does this print for n=4? <codevoid p(int n) { if (n == 0) return; System.out.print(n); p(n - 1); } </code</pre…
chevron_right

auto_awesomeAll Tools question_answerHomework Q&A menu_bookAP & SAT Prep timelineLearn Mode