CODEWITHSUNDEEP
c++recursiontime-complexity
sb15
sb15

Reputation: 313

What is the Time complexity of this recursive function?

void rec( char s1[], char s2[], int i,  map< char, int > m1, map< char, int > m2 ) {
    if ( i == n ){
        return;
    }
    rec( s1, s2, i+1, m1, m2 );
    m1[ s1[ i ] ]--;
    if ( m1[ s1[ i ] ] == 0 ){
        m1.erase( s1[ i ] );
    }
    m2[ s2[ i ] ]--;
    if ( m2[ s2[ i ] ] == 0 ){
        m2.erase( s2[ i ] );
    }
    m2[ s1[ i ] ]++;
    m1[ s2[ i ] ]++;
    if ( max( ( m1.size() ), ( m2.size() ) ) < mn ){
        mn = max( ( m1.size() ), ( m2.size() ) );
    }
    rec( s1, s2, i+1, m1, m2 );
}

mn is a global variable. What is the time complexity of this recursive function? Let's assume that n (<=20) is taken as input already.n is also global. And also assume that It is called from main with,

rec(s1,s2,0,m1,m2);

My guess is O( logn * 2^n). Is it correct?

Upvotes: 2

Views: 481

Answers (1)

peoro
peoro

Reputation: 26060

rec calls itself twice, so if N == (n-i), we can imagine the flow of calls as a binary three of height N: rec will be called exactly 2^(N+1)-1 times.

rec also calls other functions, like map<...>::size, map<...>::operator[], map<...>::erase etc. The most expensive of these functions should be O(log M), where M is the size of the map. They're called sequentially, so we need to only take into account the most expensive of these operations for every call of rec.

The final complexity will thus be O(2^N * log M), with N == (n-i) and M == max size of m1 and of m2

Upvotes: 1

Related Questions