ISRO CSE 2018 | Question: 72

Question

Consider the following C code segment

int f(int x)
{
    if(x<1) return 1;
    else return (f(x-1)+g(x));
}
int g(int x)
{
    if(x<2) return 2;
    else return (f(x-1)+g(x/2));
}

Of the following, which best describes the growth of $f(x)$ as a function of $x$ ?

1. Linear
2. Exponential
3. Quadratic
4. Cubic

Comments

is there a misprint in return statement{ if(x-1) in place of f(x-1) }?

---

Here is the correct question. 

@Arjun sir please update.

---

Ans

Answer 1

$f(x) = f(x-1) + g(x)$

$\quad =f(x-1) + f(x-1) + g(x/2)$

$\quad = 2.f(x-1) + f(x/2 -1) + g(x/4)$

$\quad \vdots$

For simplicity I remove the second term in the expansion and then tries to get a lower bound for $f(x)$.

$f(x) > 2.f(x-1)$

$\implies f(x) >2.2.f(x-2)$

$\vdots$

$\implies f(x) > 2^{x}f(1)$

$\implies f(x) > 2^x$

So, option B is true, exponential growth for $f(x).$

Comments

g(x) is exponentially decreasing, on what basis did we decide it does not effect the result and removed it ? Please support your answer with explanation or any resource. @GO Classes @Arjun @Shaik Masthan

---

@siddardha_Annapuredd

Even though $g(x)$ is decreasing, it still contributes a positive amount to $2.f(x−1)$ because $g(x)=2$ for $x<2$.

$\Rightarrow f(x) > 2^x + c \Rightarrow f(x) > 2^x$

Answer 2

if T(x) is time to execute f(x) then

T(x)=2T(x-1) + T($\frac{x}{2}$-1) + T($\frac{x}{2^2}$-1) + T($\frac{x}{2^3}$-1) +............+ T($\frac{x}{2^ (\log_{2}x)}$-1) + O(1)

 so approximately T(x)=2T(x-1) + O(1)

so it's exponential.i.e option B

Comments

But I think the time complexity isn't asked but the growth of value of f(x) with respect to 'x' is asked.

---

I think answer should be Linear,

T(x) = 2T(x-1) + some_logarithmic_order.

so Linear expansion

---

$2,4,8,16, \ldots$ is linear?

---

sir ,can i take objection in this question because i marked linear but isro answer key is exponential .

Answer 3

What future holds we don't know but we can find out by keep moving forward