Establish the time and space complexity class of the following algorithm: Func(x) if x=1 then return; for y ← 100 down to 1 do print y; Func(x-1); Func(x-1); Func(x-1);

Steps to Solve

1. Identify Base Case and Recursive Calls

The function Func(x) has a base case at $x=1$. For $x>1$, it performs a loop from 100 down to 1. This constitutes 100 iterations. In each iteration, it calls Func(x-1) three times, leading to three recursive calls for each loop iteration.

2. Calculate Time Complexity Recursion Relation

Let $T(x)$ denote the time complexity of Func(x). We can write the recurrence relation for the function:

$$ T(x) = 100 + 3 \cdot T(x-1) $$

This equation arises because the function does 100 operations in the loop plus three recursive calls.

3. Solve the Recurrence Relation

We can use the substitution method or the Master Theorem to solve this recurrence.

Using the Master Theorem, we can compare it to the form $T(n) = a \cdot T(n/b) + f(n)$ where:

• $a = 3$ (the number of recursive calls)
• $f(n) = 100$ (the operations in the loop)

In our case, we have $n=b$, so we expand as follows:

$$ T(x) = 100 + 3 \cdot T(x-1) $$

Continuing this until we hit the base case:

$$ T(x) = 100 + 3(100 + 3T(x-2)) = 100 \times 3^0 + 100 \times 3^1 + 100 \times 3^2 + \ldots + 100 \times 3^{x-2} + 3^{x-1}T(1) $$

4. Finding Closed Form

The number of terms is $x-1$, and hence it simplifies to:

$$ T(x) = 100 \sum_{k=0}^{x-2} 3^k $$

This sum can be computed using the formula for a geometric series:

$$ \sum_{k=0}^{n} r^k = \frac{r^{n+1} - 1}{r - 1} \quad \text{(for } r \neq 1\text{)} $$

Applying this formula yields:

$$ \sum_{k=0}^{x-2} 3^k = \frac{3^{x-1} - 1}{2} $$

Thus,

$$ T(x) = 100 \cdot \frac{3^{x-1} - 1}{2} + C \cdot 3^{x-1} $$

For large $x$, the dominant term dictates that:

$$ T(x) = O(3^x) $$

5. Determine Space Complexity

For space complexity, we note that each function call is stored on the call stack. For Func(x), we have a maximum depth of recursion equal to $x$. Therefore, the space complexity is:

$$ O(x) $$