Register

Recursive function

• retagged by
1,043 views
3 votes
3 votes 
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?

• retagged by
User Avatar

3 Answers

Best answer
2 votes
2 votes

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.

• selected by
User Avatar
0 votes
0 votes
  • Asymptotic Time complexity = $n^{0.5} \cdot \log_2 n$
  • Asymptotic value = $k.n^{1.5}$ where $k \approx 1.32$
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
radha gogia asked Jul 21, 2015
2,201 views
How many recursive calls are made by gcd function ?
I have already gone through the links of stackoverflow on this topic but still couldn't understand it clearly , so please explain the logic behind this .
I have already gone through the links of stackoverflow on this topic but still couldn't understand it clearly , so please explain the logic behind this .
User Avatar
0 votes
0 votes
3 answers
2
gshivam63 asked May 19, 2016
2,897 views
Of the following which best describes the growth of f(x) as a function of x?
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
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. LogarithmicB. QuadraticC. LinearD. Exponential
User Avatar
1 votes
1 votes
3 answers
4
jverma asked May 23, 2022
1,064 views
Which value of static variable is returned if it is present in return statement of a recursive function?
#include <stdio.h>int f(int n){ static int r = 0; if (n <= 0) return 1; r=n; return f(n-1) + r;}int main() { printf("output is %d", f(5)); return 0;}Ou...
User Avatar
Link Copied!