CODEWITHSUNDEEP
algorithmrecursion
Wolvy
Wolvy

Reputation: 141

Big O notations - Recursive functions

I need to find the complexity of this recursive algorithms, so, i have 3 recursive algorithms and simply just want to know the Big O Notation for them. I think i have the solution for 2 of these algorithms, just wanna check with the community.

int f1(int n)
{
    if ( n<= 1)
        return (1);
    else 
        return (n *f1(n-1))
}

I think the solution of this is O(n).

int f2 (int n)
{
    if(n<=1)
        return(1);
    else
        return(n*f2(n / 2))
}

I think the solution of this is O(Log 2 (n))

int f3 
{
    int x, i; 
    if( n <= 1)  
        return 1;  
    else 
    {
        x = f3 (n / 2);           
        for( i = 1 ; i <= n ; i++)   
         x++;        
         return x;  
    }
}

What is the complexity of this recursive algorithm, i don't have the solution for this algorithm, Can you help me?

Upvotes: 1

Views: 1686

Answers (2)

user4668606
user4668606

Reputation:

@codecrazers answer already covers up how to calculate the complexity step-by-step. But in general the Master-Theorem makes the problem a lot simpler.

To start, lets transform this code

int f3 (int n)
{
    int x, i; 
    if( n <= 1)  
        return 1;  
    else 
    {
        x = f3 (n / 2);           
        for( i = 1 ; i <= n ; i++)   
            x++;        
        return x;  
    }
}

Into a recurrence:

int f(int n)
{ 
    if( n <= 1)  
        1  
    else
        f(n / 2) + θ(n)
}

So

T(n) = T(n / 2) + θ(n)
T(n <= 1) = 1

Which is case 3, thus yielding

T(n) = θ(n)

Upvotes: 1

codecrazer
codecrazer

Reputation: 535

Your first two answer is correct. Let's do analysis for your third problem, for each times, n is divides by 2 and we need to add x for n times, so the complexity will be 1*n+1*n/2+1*n/4+.....+1=n(1+1/2+1/4+...)=O(n)

Upvotes: 1

Related Questions