1,200 views
Consider the following code:

int f(int num)
{

int result =0;                                                                                                                                                                             if(num <= 1)
return 1;
else
{
for(i=num;i>=1;i--)
result+=f(i/3);
}
return result;
}

Anyone plz explain this code line by line for input num=6????

Follow bottom-up approach in such questions. like first calculate f(0) then f(1) and so on , because there are recursive calls and functions are evaluated in post order so better start from leaf ..

f(0)=1 //obvious

f(1)=1  // obvious

f(2)= ?        i=2                                                   i=1

r=0+f(2/3)=0+f(0)=1                     r=1+f(1/3)=1+f(0)=1+1=2

f(2)=2

f(3)=?    i=3                                                i=2                                i=1

r=0+f(3/3)=0+f(1)=0+1=1        r=1+f(2/3)=1+1=2        r=2+f(1/3)=2+1=3

f(3)=3

f(4)=?

i=4                                        i=3

r=0+f(4/3)=0+f(1)=1          r=1+f(3/3)=1+f(1)=2

i=2                                                  i=1

r=2+f(2/3)=2+f(0)=3                     r=3+f(1/3)=4

f(4)=4

f(5)=?

i=5                                               i=4                                        i=3

r=0+f(5/3)=0+f(1)=1                 r=1+f(4/3)=2                       r=2+f(3/3)=2+f(1)=3

i=2                                   i=1

r=3+f(2/3)=3+1=4       r=4+f(1/3)=4+f(0)=5

f(5)=5

f(6)=?

i=6                                                  i=5                                      i=4

r=0+f(6/3)=0+f(2)=2                    r=2+f(5/3)=3                      r=3+f(4/3)=4

i=3                                                     i=2                         i=1

r=4+f(3/3)=5                                      r=5+f(2/3)=6         r=6+f(1/3)=6+f(0)=7

f(6)=7

1 comment

can you plzz explain time complexity of the above question ??
f(0)=1,f(1)=1,f(2)=2.

i=6 result=2

i=5 result=3

i=4 result=4

i=3 result=5

i=2 result=6

i=1 result=7

1
4,852 views