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

Question

int f(int x)

{

if(x<1) return 1;

else return f(x-1) +g(x/2);

}

int g(int x)

{

if(x<2) return 1;

else return f(x-1) +g(x/2);

}

a. Logarithmic

B. Quadratic

C. Linear

D. Exponential

Answer 1

f(1)=2,f(2)=3, f(3)=3  and f(10)=42  so it may  not be log or exponential or linear it should be quadratic i think

Comments

@sanjay_sharma sir, I have a problem to guessing growth like why it is not log,expo series and how do we know it is quadratic one..

---

CLEARLY if n=1 ,2,3....10   are giving u f(n)= 2,3,3,42    it can not be log as it would have been  grown like 1,1,2,3... (very slow grow)  log n

for linear its growth should be around  n 1.2.3....10

for exponential its growth would have been very large say for n=10  f(n) would have been in thousands

Answer 2

F1=G1=2

F2=G2=4

F3=G3=6

F4=G4=10

F5=G5=14

F6=G6=16

F10=G10=56

..................

.................

so this means that fn=n*logn+some constant term...

if you form recurence=fn=f(n-1)+f(n/2) which also leads nlogn

so QUADRATIC IS ANS......

OPTION B

.

.

Comments

F(0)=1 F(1)=f(0)+g(1)=1+1=2 F(2)=f(1)+g(2)=f(1)+f(1)+g(2/2)=2+2+1=5 F(3)=f(2)+g(3)=f(2)+f(2)+g(3/2)=5+5+1=11 Similarly F(4)=25 So, I didn't get what u mean.. Plz explain in detail..where I am wrong

---

f(1)=f0+g(1/2)

since it is returning int it will be g(0).

f(2)=f(1)+g(1) (not g(2)) in ur comment

for me:i hv to change f(1)=2 and so on..

---

U r using g(x) function for f(x) value f(x)=f(x-1)+g(x) and not g(x/2)

---

F(x)=F(X-1)+G(X/2) IN THE QUESTION

---

Yeah sorry, What would be the answer for this

 int f(int x)

{

if(x<1) return 1;

else return f(x-1) +g(x);

}

int g(int x)

{

if(x<2) return 1;

else return f(x-1) +g(x/2);

} 

---

DONT FOLLOW THE CHAIN EXPANSION.

FOLLOW TREE LIKE STRUCTURE FOR FIRST FEW TERMS..

THEN U WILL FIND A COMMON BEHAVIOUR

HERE

F0=1,G0=1

F1=2,G1=1

F2=5,G2=3

F3=11,G3=6

F4=25,G4=14

IT GROWS EXPONENTIAL

---

Sir I am still confused...

If f(x)=f(x-1) +g(x/2) then it grows quadratically

But if f(x)=f(x-1)+g(x) then it grows exponentially

What is the difference b/w the two.how to identify that it is growing quadratically and other is growing exponentially.

Could u also explain a variation in which it will grow logarithmically?

---

How it's growing exponentially please explain

Answer 3

x = 1, f(1) = f(0) + g(1) = 1 + 1 = 2, f(1) = 2

x = 2, f(2) = f(1) + g(2) = 2 + f(1) + g(1) = 2 + 2 + 1 = 5, f(2) = 5

x = 3, f(3) = f(2) + g(3) = 5 + f(2) + ~g(1) = 5 + 5 + 1 = 11, f(3) =11

.

.

.

.

Similarly, x = 10, f(10) = 1952

So, it's increasing exponentially.