Временная сложность рекурсивного палиндромного вопроса, C ++

Question

Мне было просто интересно, как я могу найти здесь временную сложность моей рекурсивной функции.Я знаю, что для большей части моей программы все это в постоянном времени O (1), но как рассчитать временную сложность рекурсивных функций?

int pal(int n, int temp)
{
    // Using division of 10 trick
    if(n == 0)
        return temp;

    // Build the number backwards.
    temp = (temp * 10) + (n % 10);

    // Then advance through the number.
    return pal(n / 10, temp);
}

int main()
{
    int n = 5678;
    int temp = pal(n, 0);
    if(temp == n)
       cout << "Yes it is a palindrome";
    else
       cout << "No its not a palindrome";
]

Answer 1

Это O(log(n)), где n - это число.

Но это также O(s), shere s - размер ввода (довольно стандартный в теории вычислений использование размера ввода в качестве строки)

Скомпилированный на любой существующей платформе C ++, вы также можете утверждать, что это O(k), потому что int имеет конечный размер.

Таким образом, это зависит от используемого вами соглашения.Или что бы ни показывал ваш профессор в классе.: -)