c - 找出递归函数的时间复杂度

Question

当n1是s1的长度，n2是s2的长度时，为什么这个函数的时间复杂度是O(n1*n2)？

我试图建立一个方程式但失败了。

#include <stdio.h>

int f(char* s1, int i1, char* s2, int i2) {
    if (s2[i2] == '\0')
        return 1;
    if (s1[i1] == '\0')
        return 0;
    if (s1[i1] != s2[i2])
        return f(s1, i1 + 1, s2, 0);
    return f(s1, i1+1, s2, i2+1);
}

void main() {
    printf("%d", f("hello", 0, "he", 0));
}

Answer 1

对于两次尾调用，函数将i1递增1，因此时间复杂度为O(n1)。

请注意，此函数未实现 strstr() 的变体，因为它无法找到 f("aab", 0, "ab", 0).