Question

#include <iostream>
#include <string>
using namespace std;

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

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

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

int main()
{
   system("clear");

   int num;

       // Ask the user for an input.
       cout << "\nEnter any integer: ";
       cin >> num;

       int temp = pal(num, 0);

       // Pass this through to our function.
       if(temp != num)
           cout << "\nThe number is *not* a palindrome";
       else
           cout << "\nThe number *is* a palindrome";

       cout << "\n\nAgain? (1 for yes/0 for no): ";
       cin >> again;

   cout << "\n\nPress any key to continue...";
   cin.get();

}

This program lets the user enter in any number and it will check to see if it's a palindrome or not using a recursive method. What is the time complexity of this recursive method, and justify your answer. Don't just write the big O answer, give a justification in detail.

Answer 1

pal takes input n and temporary variable temp for the recursion.

It calls recursively for each digit of the input variable n.
During these calls it finally calculates the reverse of the input value n and stores it into temp and finally returns the temp value.

In other words, pal is a function that calculates the reverse of the input n to temp and returns the value of temp when n becomes zero.

So, Number of recursive calls = Number of digits ib variable n.
Lets say Number of digits in n = d

So, Time complexity = O(Number of digits in n) = O(d)