Skip to content
GATETECH
Official PYQ · 1998Q2.12Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 1998 Q2.12 — Asymptotic Worst Case Time and Space Complexity

Explain with AI

What value would the following function return for the input x=95x=95?

Function fun (x:integer):integer;
Begin
    If x > 100 then fun = x – 10
    Else fun = fun(fun (x+11))
End;
Choose one option
View worked solution

Answer: C

The given recursive function is the well-known McCarthy 91 function, defined as:

fun(x)={x−10if x>100fun(fun(x+11))if x≤100\text{fun}(x) = \begin{cases} x - 10 & \text{if } x > 100 \\ \text{fun}(\text{fun}(x + 11)) & \text{if } x \le 100 \end{cases}

For any integer input x≤100x \le 100, this function always evaluates to 9191. Let us trace the execution for x=95x = 95:

  • fun(95)=fun(fun(106))=fun(96)\text{fun}(95) = \text{fun}(\text{fun}(106)) = \text{fun}(96)
  • fun(96)=fun(fun(107))=fun(97)\text{fun}(96) = \text{fun}(\text{fun}(107)) = \text{fun}(97)
  • fun(97)=fun(fun(108))=fun(98)\text{fun}(97) = \text{fun}(\text{fun}(108)) = \text{fun}(98)
  • fun(98)=fun(fun(109))=fun(99)\text{fun}(98) = \text{fun}(\text{fun}(109)) = \text{fun}(99)
  • fun(99)=fun(fun(110))=fun(100)\text{fun}(99) = \text{fun}(\text{fun}(110)) = \text{fun}(100)
  • fun(100)=fun(fun(111))=fun(101)=101−10=91\text{fun}(100) = \text{fun}(\text{fun}(111)) = \text{fun}(101) = 101 - 10 = 91

Thus, the function returns 9191.

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

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