ISRO2018-72

Question

Consider the following C code segment

int f(int x)
{
    if(x<1) return 1;
    else return (if(x-1)+g(x));
}
int g(int x)
{
    if(x<2) return 2;
    else return (if(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.

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).$

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 .