Algorithms · Question 14 · Hard
For the naive recursive Fibonacci function below, how many times is fib called in total (including the first call) when evaluating fib(5)?
int fib(int n) {
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}- 8
- 9
- 15
- 31
Answer and explanation
Answer: C. 15
Explanation: The number of calls C(n) satisfies C(n) = C(n-1) + C(n-2) + 1 with C(0) = C(1) = 1. This gives C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 15.
Previous: A 0/1 knapsack has capacity 7 kg. The items (weight, value) are: (1 kg, ₹1)… · Next: Using the Master theorem, what is the solution of T(n) = 3T(n/2) + n?
Practise algorithms
Try a fresh set of algorithms questions with an explanation after every answer, free and without signing up: Algorithms practice. Or sit a full placement mock test.
More algorithms questions
- Insertion sort is applied to [5, 2, 4, 6, 1, 3]. What does the array look like…
- What is the length of the Longest Common Subsequence (LCS) of the strings…
- A 0/1 knapsack has capacity 7 kg. The items (weight, value) are: (1 kg, ₹1)…
- Using the Master theorem, what is the solution of T(n) = 3T(n/2) + n?
- What is the best-case time complexity of linear search on an array of n…
- Which of the following sorting algorithms is stable in its standard…
- Which algorithm finds single-source shortest paths correctly even when some…
- What is the worst-case time complexity of merge sort on n elements?
- What is the time complexity of finding the largest element in an unsorted…
- Bubble sort is applied to the array [4, 1, 3, 2] in ascending order. What does…
More technical & programming practice
Object-Oriented Programming · DBMS · SQL · Operating Systems · Computer Networks · Software Engineering · Cloud & DevOps · GenAI Basics
LogicWiz Exams home · All practice topics · Placement mock tests · Daily 10 challenge