Official PYQ · 2021Set 2 · Q49Asymptotic Worst Case Time and Space ComplexityNAT2 marks

GATE CS 2021 Set 2 Q49 — Asymptotic Worst Case Time and Space Complexity

Consider the following $\text{ANSI C}$ program

#include <stdio.h>
int foo(int x, int y, int q) 
    {
        if ((x<=0) && (y<=0))
        return q;
        if (x<=0)
        return foo(x, y-q, q);
        if (y<=0)
        return foo(x-q, y, q);
        return foo(x, y-q, q) + foo(x-q, y, q);
    }
int main( )
{
    int r = foo(15, 15, 10);
    printf(“%d”, r);
    return 0;
}

The output of the program upon execution is _________

View worked solution

Answer: 60 : 60

We need to find the value returned by the call foo(15, 15, 10). Throughout the execution, the parameter $q = 10$ remains constant. Let us denote the function as $f(x, y)$ for simplicity.

The base cases and recursive steps are defined as follows:

If $x \le 0$ and $y \le 0$ , then $f(x, y) = q = 10$ .
If $x \le 0$ and $y > 0$ , then $f(x, y) = f(x, y-10)$ . Since $x$ remains $\le 0$ , this eventually reduces to $f(x, y') = 10$ where $y' \le 0$ . Thus, $f(x, y) = 10$ for any $x \le 0$ .
Similarly, if $y \le 0$ and $x > 0$ , then $f(x, y) = 10$ for any $y \le 0$ .
If $x > 0$ and $y > 0$ , then $f(x, y) = f(x, y-10) + f(x-10, y)$ .

Now, we compute the values bottom-up for positive arguments in steps of $10$ :

For $f(5, 5)$ :
$f(5, 5) = f(5, -5) + f(-5, 5) = 10 + 10 = 20$
For $f(15, 5)$ and $f(5, 15)$ :
$f(15, 5) = f(15, -5) + f(5, 5) = 10 + 20 = 30$
$f(5, 15) = f(5, 5) + f(-5, 15) = 20 + 10 = 30$
For $f(15, 15)$ :
$f(15, 15) = f(15, 5) + f(5, 15) = 30 + 30 = 60$

Thus, the output of the program is 60.

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

Published 10 Oct 2026

Report a correction

Browse this topic

More Asymptotic Worst Case Time and Space Complexity questions

GATE CS 2021 Set 2 Q49 — Asymptotic Worst Case Time and Space Complexity

Related questions