Code complexity

Question

Can anybody explain to me the time complexity of the following code:

cin >> n;
while(n>9)
{
    int num = n;
    int s = 0;
    while(num!=0)
    {
        s = s + num%10;
        num = num/10;
    }
    n = s;
}
cout<<n<<endl;

The above code calculates the sum of the digits of the number until the sum becomes a single digit number.

Example: 45859 = 4+5+8+5+9 = 31 = 3+1 = 4

Edit: I think that the inner loop calculating the sum of digits has O(log_base_10(n)) complexity, but the outer loop continues till the sum obtained so far is less than 10. So the total complexity depends on how many times the outer loop is going to run.. I am not able to figure that out... Some kind of mathematical gimmicks to calculate the complexity of the outer loop would help!!!

_Complextity_ by which particular aspects? From an intellectual point of view, the _complexity_ tends to be zero. — πάντα ῥεῖ, Sep 30 '16 at 18:04
You have one loop that depends on `n` (Input data set number) then it is `O(n)` as complexity time. And another loop that also depends on `n`, then the overall complexity time is `O(n^2)` ( O => Less than or equal) — Khalil Khalaf, Sep 30 '16 at 18:08
My instinct says this is `O( N * M )`, where N is the size of the initial input and M is proportional to the average value of each digit. But since M can't be higher than `9 * k`, I'd just consider it `O(N)` — KABoissonneault, Sep 30 '16 at 18:09
Computing Big O is kind of a rite of passage in programming. You won't get much useful help here on Stack Overflow unless you say what you think it is and why. Then you will likely get comments saying "You got it" or answers explaining why you are wrong from which you can probably infer the correct answer. — user4581301, Sep 30 '16 at 18:10
Can't wonder, so many people, so eager to downvote!!!! Great.. thanks for the help... — User_Targaryen, Sep 30 '16 at 18:23
Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — user4581301, Sep 30 '16 at 18:24
Downvotes because this is not useful for anyone else. SO is not a helpdesk. — Lightness Races in Orbit, Sep 30 '16 at 18:48

score 1 · Answer 1 · answered Sep 30 '16 at 18:14

1

You are calculating the sum of the digits. The number of digits in n scales with log(n).

answered Sep 30 '16 at 18:14

G. Sliepen

7,637
1
15
31

Actually it's the sum of sums of digits. If the inner loop returns a sum greater than 9 - for example 99993 sums to 9+9+9+9+3=39 - the outer loop runs again on 39. 39 sums to 3+9=12. 12 sums to 1+2=3. I think this becomes `O( log(log(n)) )` – David Sep 30 '16 at 19:36
@David: The first time the outer loop runs it takes O(log(n)) time. The second time takes indeed O(log(log(n))), and the third (if you have a very big input) O(log(log(log(n)))) and so on, but the complexity of the whole is still O(log(n)). – G. Sliepen Oct 01 '16 at 20:00
I see, you're correct. The total time worst case is proportional to the sum `O(log(n)) + O(log(log(n))) + ...` but the first term dominates and the time complexity becomes `O(log(n))`. – David Oct 01 '16 at 21:55

Code complexity

1 Answers1

Linked