Recently I wrote this code to find the sum of all the digits of the number until the number turns into a one digit number. For example: number 567, we add all the digits and we get 5+6+7 = 18, now we add all the digits of 18 and we get 1+8 = 9. We can't add anymore digits because there is only one left and thus the result is 9.
Now I am having trouble figuring out the time complexity of this recursive code. Can anyone help?
int digSum(int n)
{
if(n < 10) return n;
return digSum(digSum(n/10) + n%10);
}
It is
. But this code is really strange. It works only because ans = 1 + (n - 1)%9.
What's the reasoning behind it being
? Specifically, why is 
for all positive terms 
?
We know n + n/2 + n/4 + ..... converges to 2n. The log of the previous term means that the ratio between adjacent terms is always less than 2. Therefore your series sums to less than 2 log n.
It would be
if it was written in a proper way like
But the code from post works in T(n) = T(n / 10) + O(1) which is obviously
.