Time and Space Complexity for Recursive Algorithms

In this assignment, we will delve into the concepts of time and space complexity for recursive algorithms.

Time Complexity

As you already know, time complexity measures the time an algorithm takes to run, based on the input size. Let's explore how to analyze the time complexity of recursive algorithms:

Counting Recursive Calls

To begin, we count the number of recursive calls the algorithm makes based on the input size. Each recursive call typically contributes to the overall time complexity.

Determining the Work Done

Next, we assess the work done at each level of recursion. It involves analyzing the operations performed within each recursive call and any additional computations outside of the recursive calls.

Combining Recursive Calls and Work Done

Finally, we combine the number of recursive calls and the work done at each level to determine the overall time complexity of the recursive algorithm.

Drawing a Recursion Tree

When analyzing the time complexity of a recursive algorithm, drawing out a recursive tree can be a helpful visual tool. The recursive tree represents the sequence of recursive calls and helps us understand the number of operations performed at each level of recursion.

By examining the structure of the recursive tree, we can count the number of nodes (representing function calls) and determine the number of operations performed in each call. This allows us to estimate the algorithm's overall time complexity.

Factorial Function

Let's begin with the factorial function:

function factorial(n) {
  if (n === 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

To determine the time complexity, we consider the number of operations performed as a function of the input size (n).

In the case of the factorial function, the number of multiplications is directly proportional to n because we make n recursive calls, reducing the input size by 1 each time until reaching the base case.

Thus, the time complexity of the factorial function is O(n), indicating a linear growth rate with the input size. As the value of n increases, the number of operations and the function's runtime increase linearly.

You can see the image of the recursion tree for the Factorial function below:

Fibonacci Function

Next, let's consider the Fibonacci sequence, where each number is the sum of the two preceding ones.

function fibonacci(n) {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

As we have said, the time complexity of a recursive algorithm depends on the number of recursive calls and the work done at each level.

Let's consider the work done:

• At each level of recursion, we make two recursive calls and perform the addition operation. This means that the work done at each level is proportional to the number of recursive calls.
• The number of recursive calls at each level follows a pattern. It doubles with each increase in level.

Because the number of recursive calls doubles with each level, the time complexity can be approximated to O(2^n), where n is the input size. This indicates exponential growth with the input size.

You can see the image of the recursion tree for the Fibonacci function below:

Space Complexity

Space complexity refers to the amount of memory an algorithm requires to perform its computations. In the case of recursive algorithms, understanding space complexity involves considering the memory used for recursive function calls and auxiliary data structures.

As we have learned in the previous assignment, recursive function calls are implemented using a call stack. The call stack is a data structure that keeps track of the function calls, storing the necessary information for each call, such as local variables and the return address.

To analyze the space complexity of a recursive algorithm, we consider the maximum depth of the recursive calls, as it determines the space used by the call stack.

In some cases, additional auxiliary data structures may contribute to the space complexity. This is why it is advisable to avoid allocating O(n) space during each recursion, such as creating new arrays, and instead pass the array through the function calls and adjust pointers. Allocating O(n)space during each recursion can result in a space complexity of O(n^2), where n represents the input size. This approach can be problematic for large inputs, requiring substantial additional memory.

Now, let's break down the space complexity for both the Factorial and Fibonacci algorithms:

Space Complexity of the Factorial Algorithm:

As mentioned above, the space complexity is determined by the maximum depth of the recursive calls, which affects the height of the call stack. Each function call adds a new frame to the call stack, consuming memory.

As the factorial function makes recursive calls until it reaches the base case, the maximum depth of the recursive calls is equal to n. Therefore, the space complexity of the factorial algorithm is O(n), indicating linear space usage.

Let's see the maximum height call stack for the factorial function visually:

Space Complexity of the Fibonacci Algorithm:

At first glance, someone might mistakenly assume that the space complexity of the Fibonacci algorithm is exponential due to the presence of two recursive calls for each input value. It's easy to assume that this doubling of calls may lead to exponential growth in space usage.

However, upon closer examination, we can debunk this misconception and show that the space complexity is, in fact, linear.

When the Fibonacci algorithm is invoked with an input value of n, it doesn't make two recursive calls simultaneously. Instead, it makes one recursive call and then proceeds to the next recursive call from within the first function call.

Fibonacci Call Stack

Let's walk through the step-by-step execution of the Fibonacci algorithm, focusing on the recursive calls and the call stack using fibonacci(4):

Step 1

• We start by invoking fibonacci(4).

Step 2

• Inside the fibonacci function for n = 4, we make a recursive call to fibonacci(3).

Step 3

• Now, we are inside the fibonacci function for n = 3. From here, we make a recursive call to fibonacci(2).

Step 4

• We continue down the recursive calls and are now inside the fibonacci function for n = 2. From here, we make a recursive call to fibonacci(1).

Step 5

• We have reached the base case with n = 1 and return the value 1.

Step 6

• Now, we backtrack to the previous function call in fibonacci(2) where we left off. We have obtained the result for the recursive call fibonacci(1), which is 1. We proceed with the calculation in fibonacci(2) and make a recursive call to fibonacci(0).

Step 7

• We reach the base case with n = 0, and return the value 0.

Step 8

• Backtracking to fibonacci(2), we have the results for the recursive calls fibonacci(1) and fibonacci(0). We add these values (1 + 0) and return the sum, 1.

Step 9

• Moving up to fibonacci(3), we have the result for the recursive call fibonacci(2), which is 1. We make another recursive call from fibonacci(3) to fibonacci(1).

Step 10

• Since n == 1, we have reached the base case and return the value 1.

Step 11

• Backtracking to fibonacci(3), we add the results of the recursive calls fibonacci(2) and fibonacci(1) (1 + 1) and return the sum, which is 2.

Step 12

• Moving up to the fibonacci(4), we have the result for the recursive call fibonacci(3), which is 2, so we make another recursive call from fibonacci(4) to fibonacci(2).

Step 13

• Inside the fibonacci function for n = 2, we make a recursive call to fibonacci(1).

Step 14

• This is a base case, so we will return 1.

Step 15

• Back inside the fibonacci(2) function we make a recursive call to fibonacci(0).

Step 16

• This is also a base case since n = 0, so we return 0.

Step 17

• Backtracking to fibonacci(2), we add the results of the recursive calls fibonacci(1) and fibonacci(0) (1 + 0) and return the sum, which is 1.

Step 18

• Now, we have the results for both sides of the Fibonacci sequence. From the initial invocation of fibonacci(4), we have the results for the recursive calls fibonacci(3) and fibonacci(2), which are 2 and 1, respectively. We add these values (2 + 1) and return the sum, 3.

As observed, the height of the call stack never exceeded N. Therefore, even if the input number is significantly large, the maximum height of the call stack remains at N. This implies that the space complexity is linear, denoted as O(N).

In conclusion, analyzing the time and space complexity of recursive algorithms is crucial for understanding their efficiency and scalability. By examining the recursive tree and counting the number of operations at each level, we can determine the time complexity, which represents the growth rate of the algorithm's execution time as the input size increases. Additionally, by considering the memory usage, including the call stack and any auxiliary data structures, we can determine the space complexity, which indicates the amount of memory required by the algorithm.