time complexity=?

Question

void xyz(char *s)
{
    if(s[0]=='\0')
        return;
    xyz(s+1);
    xyz(s+1);
    printf("%c",s[0]);
}

void main()
{
    xyz("123");
}

if the input string constant is of length $n$ then what is the time complexity?

• A. $O(2^n)$
• B. $O(n^2)$
• C. $O(n)$
• D. $O(n\log n)$

Answer 1

Since in the output is of length 7 it means that there were 7 non trivial function calls in total which is (2$^{n}$ - 1) and hence the time complexity is O(2$^{n}$).

 

Comments

$T(n) = 2T(n-1) + 1$