Recursive function

Question

int fun(int n)
    {
    int s=0,i;
    if(n<=1) return 1;
    for(i=1; i*i<n; i++)
    s+=n;
    return fun(n/4)+fun(n/4)+s;
    }

 

what will be the time complexity, returning value and no. of recursive calls of the above-given code?

Comments

Is the complexity √n logn ?

Answer 1

1.Recurrence relation  for time complexity

will be T(n)=2T(n/4)+Root(n)

Because complexity of the loop is root(n)

By using case 2 of master theorem we have T(n)=theta(root(n)logn).

2.Recurrence relation  for return value

T(n)=2T(n/4)+Root(n)*n

because the function return value 2 time fun(n/4)+root(n)*n

by solving using  case 3 of master theorem we have solution of recurrence is theta(root(n)*n)

3.Recurrence relation for no of calls

T(n)=2T(n/4)+1

by solving using  case 1 of master theorem we have solution of recurrence is theta(root(n))

Correct me if i am wrong somewhere.

Comments

yup, Right!!

---

How you got recurrence relation for return value? I didn't get Root(n)*n . Please help me...

---

for(i=1; i*i<n; i++)
    s+=n;

S is incremented by value of n each time in loop and loop runs  till i^2<n or i<root(n)

So loop runs for root(n) times and each time value of s incremented by n.

Total=root(n)*n

---

thanks...! got it now:)

Answer 2

• Asymptotic Time complexity = $n^{0.5} \cdot \log_2 n$
• Asymptotic value = $k.n^{1.5}$ where $k \approx 1.32$

Comments

what will be the recurrence relation???

Answer 3

recurrence relation will be

2T(n/4)+root(n)      and T(n)=theta(root(n)iogn)

Comments

Recurrence relation for what ?