Question

Given a positive integer n, write a recursive algorithm that returns the number of the digits in n. For example, if the given number n is 12345, the algorithm should return 5. What is the time complexity of your algorithm?

Answer 1

PROGRAM -

import java.util.*;
public class abc
{
public static void main(String[] args)
{
int num;
Scanner s = new Scanner(System.in); //creating scanner object
System.out.println("Enter the number:");
num = s.nextInt(); //taking input from user using scanner object
System.out.println(num);
abc obj = new abc(); //creating object of class abc
int a = obj.fun(num); //calling the function to find no of digits in the given no
System.out.println("NO OF DIGITS IN THE GIVEN NUMBER IS : "+a);
}
int fun(int n)
{
if(n==0)
{
return 0;
}
else
{
return 1+fun(n/10); //recursively calling the function again
}
}
}

OUTPUT -  

COMPLEXITY -

The time complexity of above code is O(no-of-digits in given number).

i.e. if there are k digits in num , the complexity can be written as O(k).