GATE CS 2015 Set 3 Q39 — Asymptotic Worst Case Time and Space Complexity

To find the total number of times the function get() is invoked, we can define a recurrence relation. Let $T(n)$ denote the total number of times get() is called (including the initial call) for an input $n$.

1. Base Cases

When $n < 1$, the condition if (n < 1) is satisfied, and the function returns immediately. This still counts as $1$ invocation.

• $T(0) = 1$
• $T(-1) = 1$
• $T(-2) = 1$

2. Recurrence Relation

For $n \ge 1$, the function is invoked once, and then it recursively calls get(n-1) and get(n-3). Therefore, the recurrence relation is:

3. Step-by-Step Computation

Using the recurrence relation, we compute $T(n)$ for $n = 1$ to $6$:

• For $n = 1$:
  $T(1) = 1 + T(0) + T(-2) = 1 + 1 + 1 = 3$
• For $n = 2$:
  $T(2) = 1 + T(1) + T(-1) = 1 + 3 + 1 = 5$
• For $n = 3$:
  $T(3) = 1 + T(2) + T(0) = 1 + 5 + 1 = 7$
• For $n = 4$:
  $T(4) = 1 + T(3) + T(1) = 1 + 7 + 3 = 11$
• For $n = 5$:
  $T(5) = 1 + T(4) + T(2) = 1 + 11 + 5 = 17$
• For $n = 6$:
  $T(6) = 1 + T(5) + T(3) = 1 + 17 + 7 = 25$

Thus, the get() function is invoked a total of $25$ times before returning to main().