Big-O of Recursion: Call Stacks and Depth Analysis Quiz Quiz

Explore recursive algorithm time complexity, call stack depth, and Big-O analysis with focused questions on recursion patterns, branching factors, and performance. Ideal for those reviewing computational complexity concepts and recursive function behavior.

1. Analyzing Linear Recursion Complexity

   Given a recursive function that only calls itself once per call, such as calculating the sum of an array using 'sum(arr, n) = arr[n-1] + sum(arr, n-1)', what is the overall time complexity using Big-O notation?

   1. O(2^n)
   2. O(n^2)
   3. O(log n)
   4. O(n)

   Explanation: Linear recursion, as demonstrated in the sum example, processes each element one by one, leading to O(n) time complexity. O(log n) appears in cases like binary search where the problem size halves each time. O(n^2) and O(2^n) occur in more complex recursive patterns with multiple calls in each step or overlapping subproblems, neither of which happens in this scenario.

2. Branching Recursion Depth Analysis

   If a recursive function calls itself twice per call, like in calculating Fibonacci numbers recursively, what is the time complexity in Big-O notation when computing fib(n)?

   1. O(2^n)
   2. O(n)
   3. O(log n)
   4. O(n^2)

   Explanation: In the Fibonacci example, each call generates two more calls, forming a binary tree of calls and resulting in exponential growth, which is O(2^n). O(n) applies when there is only one call per recursion. O(n^2) is reserved for certain divide-and-conquer algorithms, while O(log n) is related to reductions by half per call, not present here.

3. Call Stack Depth in Tail Recursion

   For a tail-recursive function that sums numbers from 1 to n using an accumulator, such as 'sum(n, acc)', what is the call stack depth during execution?

   1. O(1)
   2. O(log n)
   3. O(n^2)
   4. O(n)

   Explanation: Tail-recursive functions may allow for stack optimization transforming recursion into iteration, resulting in O(1) stack depth when optimized, but without such optimization, the depth remains O(n). O(log n) would be the case if problem size halves, and O(n^2) is not relevant to call stack depth in standard recursion scenarios. O(1) only applies for fully optimized cases, not assumed by default.

4. Exponential Recursion Example

   Given a recursive function that solves the Towers of Hanoi problem for n disks by making two recursive calls and one move per call, what is the Big-O time complexity?

   1. O(2^n)
   2. O(n)
   3. O(n^2)
   4. O(n log n)

   Explanation: Towers of Hanoi involves two recursive calls for each move, doubling the number of operations per disk, and results in O(2^n) complexity. O(n) and O(n^2) would indicate polynomial relationships, not matching the exponential growth here. O(n log n) typically comes up in efficient sorting algorithms, but not in recursive problems like Hanoi.

5. Divide-and-Conquer Stack Depth

   What is the call stack depth in a divide-and-conquer recursive algorithm such as merge sort on an array of n elements?

   1. O(log n)
   2. O(n^2)
   3. O(1)
   4. O(n)

   Explanation: In merge sort, the array is continually halved until individual elements are reached, resulting in a maximum stack depth of O(log n). O(n) could occur in simple linear recursion, but merge sort utilizes the divide-and-conquer approach. O(1) is not realistic for this recursion type, and O(n^2) represents more complex recurrence relations with massive branching, not present here.