Skip to content
GATETECH
Official PYQ · 2021Set 1 · Q48Asymptotic Worst Case Time and Space ComplexityNAT2 marks

GATE CS 2021 Set 1 Q48 — Asymptotic Worst Case Time and Space Complexity

Explain with AI

Consider the following ANSI C\text{ANSI C} function:

int SimpleFunction(int Y[], int n, int x)
{
    int total = Y[0], loopIndex;
    for (loopIndex=1; loopIndex<=n-1; loopIndex++)
        total=x*total +Y[loopIndex];
    return total;
}

Let Z\textsf{Z} be an array of 1010 elements with Z[i]=1\textsf{Z}[i]=1, for all ii such that 0≤i≤90 \leq i \leq 9. The value returned by SimpleFunction(Z,10,2)\textsf{SimpleFunction(Z},10,2) is __________

View worked solution

Answer: 1023 : 1023

The given C function implements Horner's method for evaluating a polynomial of degree n−1n-1 at a point xx, where the coefficients of the polynomial are given by the array YY:

P(x)=Y[0]xn−1+Y[1]xn−2+⋯+Y[n−2]x+Y[n−1]P(x) = Y[0]x^{n-1} + Y[1]x^{n-2} + \dots + Y[n-2]x + Y[n-1]

Let's trace the execution of SimpleFunction(Z, 10, 2) where:

  • n=10n = 10
  • x=2x = 2
  • Z[i]=1Z[i] = 1 for all 0≤i≤90 \leq i \leq 9

Step-by-Step Trace:

Initially, total = Y[0] = 1.

The loop runs for loopIndex from 11 to n−1=9n-1 = 9:

  • Iteration 1 (loopIndex = 1):
    total=2×1+1=3\text{total} = 2 \times 1 + 1 = 3
  • Iteration 2 (loopIndex = 2):
    total=2×3+1=7\text{total} = 2 \times 3 + 1 = 7
  • Iteration 3 (loopIndex = 3):
    total=2×7+1=15\text{total} = 2 \times 7 + 1 = 15

In general, after kk iterations, the value of total is given by the recurrence:

Tk=2⋅Tk−1+1withT0=1T_k = 2 \cdot T_{k-1} + 1 \quad \text{with} \quad T_0 = 1

Solving this recurrence, we get:

Tk=2k+2k−1+⋯+20=2k+1−1T_k = 2^k + 2^{k-1} + \dots + 2^0 = 2^{k+1} - 1

The loop terminates after 99 iterations (when loopIndex = 9). Substituting k=9k = 9 into our formula:

T9=29+1−1=210−1=1024−1=1023T_9 = 2^{9+1} - 1 = 2^{10} - 1 = 1024 - 1 = 1023

Thus, the value returned by the function is 1023.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Asymptotic Worst Case Time and Space Complexity questions