Programming2

Question

#include<stdio.h>
int fun(int a,int b)
{
    if(b==0)
    return 0;
    if(b%2==0)
    return fun(a+a,b/2);
    return fun(a+a,b/2)+a;
}
int main()
{
    printf("%d",fun(9,11));
    return 0;
}

Comments

Why did you use getchar?

---

oh, that was given in question

I 'm removing

that means it is a old version C question

---

it will return 72+18+9 = 99 //  by traversing recursion tree topdown left to right..

---

The second return will become unreachable statement?

---

why so? ...it will depend on truth value of if(b%2==0)....isn't it..

---

yeah. i didnt notice if above that.My bad!

---

f(9,11) = 99.

---

What is the time complexity of above code?

---

O(log₂b) ?

---

yes, its TC should be log₂b, because either b is even or odd its value is decreased be /2, which means its TC is log₂b.

And space complexity should also be log₂b.

---

@Arjun Sir

for b=11, function called  4 times. So, time complexity will be $O\left ( \left \lceil logn \right \rceil \right )$

---

@srestha,

time complexity is defined for variables, if you take b=4, time complexity is simply O(1)

---

Space complexity depends on

 return fun(a+a,b/2)+a;

only on that a

So, how many times if block not called, it depends on that

So, it will be min 0 times and max log n times

---

it is not the case,

base condition for this function depends on 'b'....so entire time and space complexity depends on 'b'....and b is reducing to b/2 in every call(irrespective of truth value of if)...it not at all depends on 'a'...

---

@joshi_nitish

printf("%d",fun(9,11));

As main contains this line , u r telling O(1), rt?

U mean in progeam if specific value given, it will be O(1)

otherwise log n

right?

---

yes,

if time complexity of fun(9,11) is asked it is O(1)....for fun(a,b), it will be O(logb)

---

But space depend on a, not b

I disagree in this point

Because we add and store the bits, space required for that

b not require any storing

---

@srestha Space complexity usually (always for GATE purpose) refers to the auxiliary space and not the space required for storing the inputs. Here, (or usually for most recursive codes), it depends on the maximum recursion depth -- which in turn determines the no. of times activation record (we can assume activation record size as constant as long as there are no no local variables created) gets created simultaneously. You can see the answer update.

Answer 1

99 is the correct answer

---

The given code is actually doing just multiplication without using '*'. We can $a*b$ by adding $a$ to $a$, $b-1$ times. The given code is a smarter way to do this reducing the time complexity to $O(\log b)$ instead of $O(b)$ for the naive approach. The same code also works for doing power function, if we replace $+$ with $\times$.

Answer 2

Answer is 99

fun(9,11)->fun(18,5)+9->fun(36,2)+18->fun(72,1)->fun(144,0)+72